# UVa 897

## Contents

## 897 - Anagrammatic Primes[edit]

## Summary[edit]

As the problem states, *Anagrammatic Primes* are those primes of which every permutation is prime. So, 113 is *Anagrammatic Prime* because permutations of 113: 113, 131, 311 are primes. In this way, 47 is not an *Anagrammatic Prime*.

## Explanation[edit]

**First**, create a prime list for numbers under 10,000,000(1e7). Then check every prime if they are *Anagrammatic* or not. This way, store all the *Anagrammatic Primes* below 1e7. To check if a prime *Anagrammatic* or not, make a function which inputs a number and checks all of its permutations if they are all primes or not. If yes, return true; else return false. And then for the problem's input search the first *Anagrammatic Prime* greater than the input.

Cleverly, you can run the sieve only for first 1000 numbers. Because there is no *Anagrammatic Prime* "ap" such that, 991 >= ap > 1e7.
And, in your *Anagrammatic Checker*, for any prime greater than 2, if the number contains any even digit(0,2,4,6,8) it should return false. This helps reducing runtime too.

**Second**, just create the *Anagrammatic Prime* list in another program and keep the list in an array in your present program. This reduces runtime.

## Gotchas[edit]

Sometimes, the answer would not be the same length as your input is. If that's the case output 0. (as the problem states)

## Implementations[edit]

You can generate the permutations by backtracking. However, if you are using C++, STL includes a function called *next_permutation()*.

## Input[edit]

10 16 900 113 8000000 0

## Output[edit]

11 17 919 131 0