Ormiston pairs: Difference between revisions
Added C
(Ormiston pairs in FreeBASIC) |
(Added C) |
||
Line 113:
3722 Ormiston pairs below 10000000
53369 non-Ormiston "0 MOD 18" pairs bwlow 10000000
</pre>
=={{header|C}}==
{{trans|Wren}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <locale.h>
bool *sieve(int limit) {
int i, p;
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;
}
}
return c;
}
typedef struct {
char digs[20];
int count;
} digits;
digits getDigits(int n) {
if (n == 0) return (digits){ {0}, 1 };
digits d;
d.count = 0;
while (n > 0) {
d.digs[d.count++] = n % 10;
n = n / 10;
}
return d; // note digits are in reverse order
}
typedef struct {
int x;
int y;
} pair;
int main() {
const int limit = 1000000000;
int i, j, k, pc = 0, count = 0, count2 = 0, p1, p2, key1, key2;
digits d;
bool *c = sieve(limit);
for (i = 0; i < limit; ++i) {
if (!c[i]) ++pc;
}
int *primes = (int *)malloc(pc * sizeof(int));
for (i = 0, j = 0; i < limit; ++i) {
if (!c[i]) primes[j++] = i;
}
pair orm30[30];
int counts[5];
j = 100000;
for (i = 0; i < pc-1; ++i) {
p1 = primes[i];
p2 = primes[i+1];
if ((p2 - p1) % 18) continue;
key1 = 1;
d = getDigits(p1);
for (k = 0; k < d.count; ++k) key1 *= primes[d.digs[k]];
key2 = 1;
d = getDigits(p2);
for (k = 0; k < d.count; ++k) key2 *= primes[d.digs[k]];
if (key1 == key2) {
if (count < 30) orm30[count] = (pair){p1, p2};
if (p1 >= j) {
counts[count2++] = count;
j *= 10;
}
++count;
}
}
counts[count2] = count;
printf("First 30 Ormiston pairs:\n");
setlocale(LC_NUMERIC, "");
for (i = 0; i < 30; ++i) {
printf("[%'6d, %'6d] ", orm30[i].x, orm30[i].y);
if (!((i+1) % 3)) printf("\n");
}
printf("\n");
j = 100000;
for (i = 0; i < 5; ++i) {
printf("%'d Ormiston pairs before %'d\n", counts[i], j);
j *= 10;
}
free(c);
free(primes);
return 0;
}</syntaxhighlight>
{{out}}
<pre>
First 30 Ormiston pairs:
[ 1,913, 1,931] [18,379, 18,397] [19,013, 19,031]
[25,013, 25,031] [34,613, 34,631] [35,617, 35,671]
[35,879, 35,897] [36,979, 36,997] [37,379, 37,397]
[37,813, 37,831] [40,013, 40,031] [40,213, 40,231]
[40,639, 40,693] [45,613, 45,631] [48,091, 48,109]
[49,279, 49,297] [51,613, 51,631] [55,313, 55,331]
[56,179, 56,197] [56,713, 56,731] [58,613, 58,631]
[63,079, 63,097] [63,179, 63,197] [64,091, 64,109]
[65,479, 65,497] [66,413, 66,431] [74,779, 74,797]
[75,913, 75,931] [76,213, 76,231] [76,579, 76,597]
40 Ormiston pairs before 100,000
382 Ormiston pairs before 1,000,000
3,722 Ormiston pairs before 10,000,000
34,901 Ormiston pairs before 100,000,000
326,926 Ormiston pairs before 1,000,000,000
</pre>
| |||