UVa 897

From Algorithmist
Jump to navigation Jump to search

897 - Anagrammatic Primes[edit]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=838

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