Cuban primes: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Faster prime testing, big speed boost) |
|||
Line 132: | Line 132: | ||
The 100,000 cuban prime is: 1,792,617,147,127 |
The 100,000 cuban prime is: 1,792,617,147,127 |
||
</pre> |
</pre> |
||
=={{header|C}}== |
|||
{{trans|C++}} |
|||
<lang c>#include <limits.h> |
|||
#include <math.h> |
|||
#include <stdbool.h> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
typedef long long llong_t; |
|||
struct PrimeArray { |
|||
llong_t *ptr; |
|||
size_t size; |
|||
size_t capacity; |
|||
}; |
|||
struct PrimeArray allocate() { |
|||
struct PrimeArray primes; |
|||
primes.size = 0; |
|||
primes.capacity = 10; |
|||
primes.ptr = malloc(primes.capacity * sizeof(llong_t)); |
|||
return primes; |
|||
} |
|||
void deallocate(struct PrimeArray *primes) { |
|||
free(primes->ptr); |
|||
primes->ptr = NULL; |
|||
} |
|||
void push_back(struct PrimeArray *primes, llong_t p) { |
|||
if (primes->size >= primes->capacity) { |
|||
size_t new_capacity = (3 * primes->capacity) / 2 + 1; |
|||
llong_t *temp = realloc(primes->ptr, new_capacity * sizeof(llong_t)); |
|||
if (NULL == temp) { |
|||
fprintf(stderr, "Failed to reallocate the prime array."); |
|||
exit(1); |
|||
} else { |
|||
primes->ptr = temp; |
|||
primes->capacity = new_capacity; |
|||
} |
|||
} |
|||
primes->ptr[primes->size++] = p; |
|||
} |
|||
int main() { |
|||
const int cutOff = 200, bigUn = 100000, chunks = 50, little = bigUn / chunks; |
|||
struct PrimeArray primes = allocate(); |
|||
int c = 0; |
|||
bool showEach = true; |
|||
llong_t u = 0, v = 1, i; |
|||
push_back(&primes, 3); |
|||
push_back(&primes, 5); |
|||
printf("The first %d cuban primes:\n", cutOff); |
|||
for (i = 1; i < LLONG_MAX; ++i) { |
|||
bool found = false; |
|||
llong_t mx = ceil(sqrt(v += (u += 6))); |
|||
llong_t j; |
|||
for (j = 0; j < primes.size; ++j) { |
|||
if (primes.ptr[j] > mx) { |
|||
break; |
|||
} |
|||
if (v % primes.ptr[j] == 0) { |
|||
found = true; |
|||
break; |
|||
} |
|||
} |
|||
if (!found) { |
|||
c += 1; |
|||
if (showEach) { |
|||
llong_t z; |
|||
for (z = primes.ptr[primes.size - 1] + 2; z <= v - 2; z += 2) { |
|||
bool fnd = false; |
|||
for (j = 0; j < primes.size; ++j) { |
|||
if (primes.ptr[j] > mx) { |
|||
break; |
|||
} |
|||
if (z % primes.ptr[j] == 0) { |
|||
fnd = true; |
|||
break; |
|||
} |
|||
} |
|||
if (!fnd) { |
|||
push_back(&primes, z); |
|||
} |
|||
} |
|||
push_back(&primes, v); |
|||
printf("%11lld", v); |
|||
if (c % 10 == 0) { |
|||
printf("\n"); |
|||
} |
|||
if (c == cutOff) { |
|||
showEach = false; |
|||
printf("\nProgress to the %dth cuban prime: ", bigUn); |
|||
} |
|||
} |
|||
if (c % little == 0) { |
|||
printf("."); |
|||
if (c == bigUn) { |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
printf("\nThe %dth cuban prime is %lld\n", c, v); |
|||
deallocate(&primes); |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre>The first 200 cuban primes: |
|||
7 19 37 61 127 271 331 397 547 631 |
|||
919 1657 1801 1951 2269 2437 2791 3169 3571 4219 |
|||
4447 5167 5419 6211 7057 7351 8269 9241 10267 11719 |
|||
12097 13267 13669 16651 19441 19927 22447 23497 24571 25117 |
|||
26227 27361 33391 35317 42841 45757 47251 49537 50311 55897 |
|||
59221 60919 65269 70687 73477 74419 75367 81181 82171 87211 |
|||
88237 89269 92401 96661 102121 103231 104347 110017 112327 114661 |
|||
115837 126691 129169 131671 135469 140617 144541 145861 151201 155269 |
|||
163567 169219 170647 176419 180811 189757 200467 202021 213067 231019 |
|||
234361 241117 246247 251431 260191 263737 267307 276337 279991 283669 |
|||
285517 292969 296731 298621 310087 329677 333667 337681 347821 351919 |
|||
360187 368551 372769 374887 377011 383419 387721 398581 407377 423001 |
|||
436627 452797 459817 476407 478801 493291 522919 527941 553411 574219 |
|||
584767 590077 592741 595411 603457 608851 611557 619711 627919 650071 |
|||
658477 666937 689761 692641 698419 707131 733591 742519 760537 769627 |
|||
772669 784897 791047 812761 825301 837937 847477 863497 879667 886177 |
|||
895987 909151 915769 925741 929077 932419 939121 952597 972991 976411 |
|||
986707 990151 997057 1021417 1024921 1035469 1074607 1085407 1110817 1114471 |
|||
1125469 1155061 1177507 1181269 1215397 1253887 1281187 1285111 1324681 1328671 |
|||
1372957 1409731 1422097 1426231 1442827 1451161 1480519 1484737 1527247 1570357 |
|||
Progress to the 100000th cuban prime: .................................................. |
|||
The 100000th cuban prime is 1792617147127</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |