Erdős-primes: Difference between revisions
Added C
(→{{header|Palo Alto Tiny BASIC}}: Added a solution.) |
(Added C) |
||
Line 408:
24 2411
25 2437
</pre>
=={{header|C}}==
{{trans|Wren}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <locale.h>
#define LIMIT 1000000
bool isPrime(int n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
int d = 5;
while (d*d <= n) {
if (n%d == 0) return false;
d += 2;
if (n%d == 0) return false;
d += 4;
}
return true;
}
int *primeSieve(int limit, int *length) {
int i, p, *primes;
int j, pc = 0;
limit++;
// True denotes composite, false denotes prime.
bool *c = calloc(limit, sizeof(bool)); // all false by default
c[0] = true;
c[1] = true;
for (i = 4; i < limit; i += 2) c[i] = true;
p = 3; // Start from 3.
while (true) {
int p2 = p * p;
if (p2 >= limit) break;
for (i = p2; i < limit; i += 2 * p) c[i] = true;
while (true) {
p += 2;
if (!c[p]) break;
}
}
for (i = 0; i < limit; ++i) {
if (!c[i]) ++pc;
}
primes = (int *)malloc(pc * sizeof(int));
for (i = 0, j = 0; i < limit; ++i) {
if (!c[i]) primes[j++] = i;
}
free(c);
*length = pc;
return primes;
}
int main() {
int i, j, fact, p, pc, lc, ec = 0, ll = 2500, show = 7875;
bool found;
int *primes = primeSieve(LIMIT, &pc);
int *erdos = (int *)malloc(show * sizeof(int));
for (i = 0; i < pc && ec < show; ++i) {
p = primes[i];
j = 1;
fact = 1;
found = true;
while (fact < p) {
if (isPrime(p-fact)) {
found = false;
break;
}
++j;
fact *= j;
}
if (found) erdos[ec++] = p;
}
for (i = 0; i < ec; ++i) {
if (erdos[i] >= ll) {
lc = i;
break;
}
}
setlocale(LC_NUMERIC, "");
printf("The %'d Erdős primes under %'d are:\n", lc, ll);
for (i = 0; i < lc; ++i) {
printf("%6d ", erdos[i]);
if (!((i+1)%10)) printf("\n");
}
printf("\n\nThe %'dth Erdős prime is %'d.\n", show, erdos[show-1]);
free(primes);
free(erdos);
return 0;
}</syntaxhighlight>
{{out}}
<pre>
The 25 Erdős primes under 2,500 are:
2 101 211 367 409 419 461 557 673 709
769 937 967 1009 1201 1259 1709 1831 1889 2141
2221 2309 2351 2411 2437
The 7,875th Erdős prime is 999,721.
</pre>
| |||