diff options
| -rw-r--r-- | euler51.c | 113 |
1 files changed, 113 insertions, 0 deletions
diff --git a/euler51.c b/euler51.c new file mode 100644 index 0000000..dd13881 --- /dev/null +++ b/euler51.c @@ -0,0 +1,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; + } +} |