題意：給出一個長度，要求輸出這樣的所有素數n，while(n){isprime(n); n /= 10;}.
首先我們可以知道對于n的第一位一定是2 3 5 7中的一個(必須是素數),然后后面的每一位一定是奇數,不然不可能是素數。
到這基本就OK了。然后根據位數遞歸解決(有人叫dfs或bfs。我還是習慣叫遞歸-_-,無視我把)。
這個貼下官方的代碼吧。(比較簡單，自己先想想哦)
CODE
1
We use a recursive search to build superprimes of length n from superprimes of length n-1 by adding a 1, 3, 7, or 9. (Numbers ending in any other digit are divisible by 2 or 5.) Since there are so few numbers being tested, a simple primality test suffices.
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6#include <assert.h>
7
8FILE *fout;
9
10int
11isprime(int n)
12
{
13
int i;
14
15 if(n == 2)
16 return 1;
17
18 if(n%2 == 0)
19 return 0;
20
21 for(i=3; i*i <= n; i+=2)
22 if(n%i == 0)
23 return 0;
24
25 return 1;
26
}
27
28/**//* print all sprimes possible by adding ndigit digits to the number n */
29void
30sprime(int n, int ndigit)
31{
32
if(ndigit == 0) {
33 fprintf(fout, "%d\n", n);
34 return;
35
}
36
37 n *= 10;
38 if(isprime(n+1))
39 sprime(n+1, ndigit-1);
40 if(isprime(n+3))
41 sprime(n+3, ndigit-1);
42 if(isprime(n+7))
43 sprime(n+7, ndigit-1);
44 if(isprime(n+9))
45 sprime(n+9, ndigit-1);
46}
47
48void
49main(void)
50{
51 int n;
52 FILE *fin;
53
54 fin = fopen("sprime.in", "r");
55 assert(fin != NULL);
56 fout = fopen("sprime.out", "w");
57 assert(fout != NULL);
58
59 fscanf(fin, "%d", &n);
60
61 sprime(2, n-1);
62 sprime(3, n-1);
63 sprime(5, n-1);
64 sprime(7, n-1);
65 exit (0);
66}
67
68