Ormiston triples: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: Added a Haskell draft) |
(Added C) |
||
Line 23: | Line 23: | ||
* [[Ormiston pairs]] |
* [[Ormiston pairs]] |
||
<br> |
<br> |
||
=={{header|C}}== |
|||
{{trans|Wren}} |
|||
Run time about 83 seconds. |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <stdbool.h> |
|||
#include <stdint.h> |
|||
#include <locale.h> |
|||
bool *sieve(uint64_t limit) { |
|||
uint64_t 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) { |
|||
uint64_t 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(uint64_t 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 |
|||
} |
|||
int main() { |
|||
const uint64_t limit = 10000000000; |
|||
uint64_t i, j, pc = 0, p1, p2, p3, key1, key2, key3; |
|||
int k, count, count2; |
|||
digits d; |
|||
bool *c = sieve(limit); |
|||
for (i = 0; i < limit; ++i) { |
|||
if (!c[i]) ++pc; |
|||
} |
|||
uint64_t *primes = (uint64_t *)malloc(pc * sizeof(uint64_t)); |
|||
for (i = 0, j = 0; i < limit; ++i) { |
|||
if (!c[i]) primes[j++] = i; |
|||
} |
|||
free(c); |
|||
uint64_t orm25[25]; |
|||
int counts[2]; |
|||
j = limit/10; |
|||
for (i = 0; i < pc-2; ++i) { |
|||
p1 = primes[i]; |
|||
p2 = primes[i+1]; |
|||
p3 = primes[i+2]; |
|||
if ((p2 - p1) % 18 || (p3 - p2) % 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) continue; |
|||
key3 = 1; |
|||
d = getDigits(p3); |
|||
for (k = 0; k < d.count; ++k) key3 *= primes[d.digs[k]]; |
|||
if (key2 == key3) { |
|||
if (count < 25) orm25[count] = p1; |
|||
if (p1 >= j) { |
|||
counts[count2++] = count; |
|||
j *= 10; |
|||
} |
|||
++count; |
|||
} |
|||
} |
|||
counts[count2] = count; |
|||
printf("Smallest members of first 25 Ormiston triples:\n"); |
|||
setlocale(LC_NUMERIC, ""); |
|||
for (i = 0; i < 25; ++i) { |
|||
printf("%'10ld ", orm25[i]); |
|||
if (!((i+1) % 5)) printf("\n"); |
|||
} |
|||
printf("\n"); |
|||
j = limit/10; |
|||
for (i = 0; i < 2; ++i) { |
|||
printf("%'d Ormiston triples before %'ld\n", counts[i], j); |
|||
j *= 10; |
|||
printf("\n"); |
|||
} |
|||
free(primes); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Smallest members of first 25 Ormiston triples: |
|||
11,117,123 12,980,783 14,964,017 32,638,213 32,964,341 |
|||
33,539,783 35,868,013 44,058,013 46,103,237 48,015,013 |
|||
50,324,237 52,402,783 58,005,239 60,601,237 61,395,239 |
|||
74,699,789 76,012,879 78,163,123 80,905,879 81,966,341 |
|||
82,324,237 82,523,017 83,279,783 86,050,781 92,514,341 |
|||
368 Ormiston triples before 1,000,000,000 |
|||
4,925 Ormiston triples before 10,000,000,000 |
|||
</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |