1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
/*
ID: mytbk921
LANG: C
TASK: sprime
*/
#include <stdio.h>
#include <stdlib.h>
static int sqrmod(int b, int n)
{
long long t = b;
t *= t;
return t % n;
}
int expmod(int b, int e, int n)
{
long long t;
if (e == 0)
return 1;
t = expmod(b, e/2, n);
t = sqrmod(t, n);
if (e%2) {
t *= b;
t %= n;
}
return t;
}
int mr_test(int test, int n)
{
int s, r;
long long t;
r = 0;
for (s = n-1; s%2==0; s/=2)
r++;
t = expmod(test, s, n);
if (t==1)
return 1;
while (r--) {
if (t==n-1)
return 1;
t = sqrmod(t, n);
}
return 0;
}
/* Miller-Rabin test:
* return 1 if considered prime,
* otherwise return the proof of non-prime
*/
int miller_rabin(const int n)
{
int r;
int i;
if (n==2 || n==3 || n==5 || n==7)
return 1;
if (n%2==0 || n==1)
return 0;
for (i=0; i<100; i++) {
do {
r = rand() % n;
} while (r==0 || r==1 || r==n-1);
if (!mr_test(r, n))
return r;
}
return 1;
}
static int isprime(int n) { return miller_rabin(n)==1; }
FILE *fin, *fout;
void search_sprime(int N, int s)
{
int i;
if (N == 0) {
fprintf(fout, "%d\n", s);
return;
}
if (s == 0) {
search_sprime(N-1, 2);
}
for (i=1; i<=9; i+=2) {
if (isprime(s*10+i))
search_sprime(N-1, s*10+i);
}
}
int main()
{
int N;
fin = fopen("sprime.in", "r");
fout = fopen("sprime.out", "w");
fscanf(fin, "%d", &N);
fclose(fin);
search_sprime(N, 0);
fclose(fout);
return 0;
}
|
