Sum of two adjacent numbers are primes: Difference between revisions

Content added Content deleted
(→‎{{header|Wren}}: Recoded to do extra credit.)
(→‎{{header|C}}: Recoded to do extra credit.)
Line 331: Line 331:


=={{header|C}}==
=={{header|C}}==
{{trans|Wren}}
{{trans|Go}}
<lang c>#include <stdio.h>
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <math.h>


#define TRUE 1
#define TRUE 1
#define FALSE 0
#define FALSE 0


typedef int bool;
int isPrime(int n) {

if (n < 2) return FALSE;
void primeSieve(int *c, int limit, bool processEven, bool primesOnly) {
if (!(n%2)) return n == 2;
if (!(n%3)) return n == 3;
int i, ix, p, p2;
int d = 5;
limit++;
while (d*d <= n) {
c[0] = TRUE;
⚫
c[1] = TRUE;
⚫
if (!(n%d)) return FALSE;
if (processEven) {
⚫
d += 2;
if (!(n%d)) return FALSE;
for (i = 4; i < limit; i +=2) c[i] = TRUE;
d += 4;
}
⚫
p = 3;
while (TRUE) {
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;
⚫
}
}
if (primesOnly) {
/* move the actual primes to the front of the array */
c[0] = 2;
for (i = 3, ix = 1; i < limit; i += 2) {
if (!c[i]) c[ix++] = i;
}
}
}
⚫
return TRUE;
}
}


int main() {
int main() {
int count = 0, n = 1;
int i, p, hp, n = 10000000;
int limit = (int)(log(n) * (double)n * 1.2); /* should be more than enough */
int *primes = (int *)calloc(limit, sizeof(int));
primeSieve(primes, limit-1, FALSE, TRUE);
printf("The first 20 pairs of natural numbers whose sum is prime are:\n");
printf("The first 20 pairs of natural numbers whose sum is prime are:\n");
while (count < 20) {
for (i = 1; i <= 20; ++i) {
if (isPrime(2*n + 1)) {
p = primes[i];
printf("%2d + %2d = %2d\n", n, n + 1, 2*n + 1);
hp = p / 2;
count++;
printf("%2d + %2d = %2d\n", hp, hp+1, p);
⚫
}
⚫
n++;
}
}
printf("\nThe 10 millionth such pair is:\n");
p = primes[n];
hp = p / 2;
printf("%2d + %2d = %2d\n", hp, hp+1, p);
free(primes);
return 0;
return 0;
}</lang>
}</lang>
Line 387: Line 410:
35 + 36 = 71
35 + 36 = 71
36 + 37 = 73
36 + 37 = 73

The 10 millionth such pair is:
89712345 + 89712346 = 179424691
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Sum_of_two_adjacent_numbers_are_primes"