66 lines
1.4 KiB
C
66 lines
1.4 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
#include <string.h>
|
|
|
|
typedef struct {
|
|
int* digits;
|
|
int length;
|
|
} Transcendental;
|
|
|
|
Transcendental e;
|
|
|
|
|
|
void calcDigits(unsigned int numDigits) {
|
|
// declare dynamic array to hold digits of e
|
|
e.length = numDigits;
|
|
e.digits = (int *) malloc(numDigits);
|
|
|
|
// spigot algorithm
|
|
int N = numDigits + 9, a[numDigits+9], x = 0;
|
|
for (int n = N - 1; n > 0; --n) {
|
|
a[n] = 1;
|
|
}
|
|
a[1] = 2, a[0] = 0;
|
|
while (N > 9) {
|
|
int n = N--;
|
|
while (--n) {
|
|
a[n] = x % n;
|
|
x = 10 * a[n-1] + x/n;
|
|
}
|
|
// populate array with digits
|
|
e.digits[(numDigits+8) - N] = x%10;
|
|
}
|
|
}
|
|
|
|
bool isPrime(unsigned long n) {
|
|
// screen out numbers that can't be prime
|
|
if (n != 2 && n != 3 && n % 6 != 1 && n % 6 != 5) {
|
|
return false;
|
|
}
|
|
// check factors up to square root
|
|
for (unsigned int i=3; (unsigned long) i * i <= n; i++) {
|
|
if (n % i == 0) return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
int main() {
|
|
//get first 1000 digits of e
|
|
calcDigits(1000);
|
|
int pos = 0;
|
|
unsigned long currentTen = 2;
|
|
while(pos < e.length){
|
|
currentTen = (currentTen % 1000000000) * 10 + e.digits[pos];
|
|
if(pos >= 9 && isPrime(currentTen)) {
|
|
printf("found! %lu\n", currentTen);
|
|
free(e.digits);
|
|
return 0;
|
|
}
|
|
pos++;
|
|
}
|
|
printf("failed to find :(\n");
|
|
free(e.digits);
|
|
return 1;
|
|
}
|