想吃冰卻又敏感保護不足?來自星星的你也會打廣告?法人:14檔今年本業虧定了睽違25天終開會 立院...
2012-12-12 08:35:31 人氣(108) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][sieve] 897 - Anagrammatic Primes

0
收藏
0
推薦


  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;
}

897Anagrammatic Primessieve
台長:Morris
人氣(108) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][二項式定理][log] 10883 - Supermean
此分類上一篇:[UVA][遞迴] 11173 - Grey Codes

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文