[UVA][sieve] 897 - Anagrammatic Primes
Anagrammatic Primes
| Anagrammatic Primes |
A number greater than one is prime if it has no divisors other than itself and 1 (note that 1 is not prime). For example, 23 is prime and 35 is not prime because 35 = 7 × 5. When the digits of a number are rearranged, its primeness may change - for example, 35 is not prime but 53 is. For this problem, you have to find numbers which are prime no matter how you rearrange their digits. For example, all of the numbers 113, 131 and 311 are prime, so we say that 113 is an anagrammatic prime (also 131 and 311 are anagrammatic primes).
Input
Each line of input will contain a single positive number n, less than 10,000,000. You must find the first anagrammatic prime which is larger than n and less than the next power of 10 greater than n. The input will be terminated by a line consisting of a single `0'.
Output
For each number in the input, one line of output must be produced. This output line should contain either the next anagrammatic prime, as described above, or `0' if there is no anagrammatic prime in the range defined.
Sample Input
10 16 900 113 8000000 0
Sample Output
11 17 919 131 0
事實上這些質數不會超過一千。
而且只有二十二個。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define LL long long
#define maxL (10000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
int anaP[30], at = 0;
void sieve() {
register int i, j, k;
SET(1);
int n = 10000000;
for(i = 2; i < n; i++) {
if(!GET(i)) {
for(k = n/i, j = i*k; k >= i; k--, j -= i)
SET(j);
}
}
char buf[10], len, flag;
for(i = 2; i < n; i++) {
if(!GET(i)) {
sprintf(buf, "%d", i);
len = strlen(buf);
sort(buf, buf+len);
flag = 0;
do {
sscanf(buf, "%d", &j);
if(GET(j)) flag = 1;
} while(next_permutation(buf, buf+len) && !flag);
if(!flag)
anaP[at++] = i;
}
}
}
main() {
sieve();
int n, i;
while(scanf("%d", &n) == 1 && n) {
if(n > anaP[at-1]) {
puts("0");
continue;
}
int n10 = (int)pow(10, (int)log10(n)+1);
for(i = 0; i < at; i++) {
if(anaP[i] > n && anaP[i] < n10) {
printf("%d\n", anaP[i]);
break;
}
}
if(i == at)
puts("0");
}
return 0;
}