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
113
114
115
116
117
118
119
120
121
122
123
124
|
/*
ID: mytbk921
LANG: C
TASK: pprime
*/
#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;
}
int make_palindrome(int half, int odd)
{
int s = half;
int r = (odd)?half/10:half;
while (r) {
s = s*10+(r%10);
r /= 10;
}
return s;
}
int main()
{
FILE *fin, *fout;
int a, b;
int i,j;
int base, base_max;
int stopped = 0;
fin = fopen("pprime.in", "r");
fout = fopen("pprime.out", "w");
fscanf(fin, "%d%d", &a, &b);
for (base=1; make_palindrome(base, 1)<a; base*=10)
;
base /= 10;
while (!stopped) {
base_max = base*10-1;
for (j=1; j>=0; j--) {
for (i=base; i<=base_max; i++) {
int t = make_palindrome(i, j);
if (t<a)
continue;
if (t>b) {
stopped = 1;
break;
}
if (miller_rabin(t) == 1)
fprintf(fout, "%d\n", t);
}
}
base *= 10;
}
fclose(fout);
return 0;
}
|
