38 lines
622 B
Text
38 lines
622 B
Text
/* modular exponentiation */
|
|
define p(b, e, m) {
|
|
auto r
|
|
for (r = 1; e > 0; e /= 2) {
|
|
if (e % 2 == 1) r = r * b % m
|
|
b = b * b % m
|
|
}
|
|
return(r)
|
|
}
|
|
|
|
/* cache for the primes found */
|
|
p[0] = 7
|
|
|
|
define d(n) {
|
|
auto i, p, r;
|
|
if (p(10, n - 1, n) == 1) {
|
|
for (r = sqrt(n); (p = p[i]) <= r; ++i) if (n % p == 0) return(1)
|
|
p[++l] = n
|
|
}
|
|
return(0)
|
|
}
|
|
|
|
/* wheel to skip multiples of 2, 3, and 5 */
|
|
w[0] = 4
|
|
w[1] = 2
|
|
w[2] = 4
|
|
w[3] = 2
|
|
w[4] = 4
|
|
w[5] = 6
|
|
w[6] = 2
|
|
w[7] = 6
|
|
|
|
for (n = p[0]; c != 10; i = (i + 1) % 8) {
|
|
if (d(n += w[i]) == 1) {
|
|
n
|
|
c += 1
|
|
}
|
|
}
|