blob: dd13881a088b0495b1a6c2822b519f08a4ebc1cd (
plain)
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
|
#include <stdio.h>
#define MAXLEN 20
unsigned long long p10[MAXLEN];
#define MAXNUM 100000000
int nprimes;
int primes[MAXNUM];
void getprimes()
{
primes[0] = 2;
nprimes = 1;
for (int i = 3; i <= MAXNUM; i+=2) {
int isprime = 1;
for (int j = 0; j < nprimes; j++) {
if (primes[j] * primes[j] > i)
break;
if (i % primes[j] == 0) {
isprime = 0;
break;
}
}
if (isprime) {
primes[nprimes] = i;
nprimes ++;
}
}
}
void init()
{
int i;
p10[0] = 1;
for (i = 1; i < MAXLEN; i++)
p10[i] = p10[i-1] * 10;
getprimes();
}
int isprime(unsigned long long x)
{
for (int i = 0; primes[i] * primes[i] <= x; i++) {
if (x % primes[i] == 0)
return 0;
}
return 1;
}
static int getdigits(unsigned long long x, int d[])
{
int nd = 0;
while (x > 0) {
d[nd] = x % 10;
nd++;
x /= 10;
}
return nd;
}
/* the number of digits to be replaced must be multiple of 3,
* otherwise at least 3 of the replaced numbers are multiple of 3
*/
int search3(unsigned long long x)
{
int digits[40];
int nd;
int i, j, k;
unsigned long long t;
nd = getdigits(x, digits);
for (i = 0; i < nd-2; i++) {
if (digits[i] >= 3) /* at most 7 numbers */
continue;
for (j = i+1; j < nd-1; j++) {
if (digits[j] != digits[i])
continue;
for (k = j+1; k < nd; k++) {
if (digits[k] != digits[i])
continue;
unsigned long long delta = p10[i] + p10[j] + p10[k];
int cnt = 1; /* assume x is prime */
t = x;
int tmp = digits[i] + 1;
while (tmp < 10) {
t += delta;
if (isprime(t))
cnt++;
tmp++;
}
if (cnt >= 8)
return 1;
}
}
}
return 0;
}
int main()
{
unsigned long long t = 1001;
init();
while (1) {
if (isprime(t) && search3(t)) {
printf("%lld\n", t);
return 0;
}
t += 2;
}
}
|
