题意:给出一个长度,要求输出这样的所有素数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
8
FILE *fout;
9
10
int
11
isprime(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 */
29
void
30
sprime(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
48
void
49
main(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