Smarandache-Wellin primes: Difference between revisions
Content added Content deleted
(→{{header|Go}}: Changed in line with Wren solution of which it is a translation.) |
(→{{header|C}}: Changed in line with Wren solution of which it is a translation.) |
||
Line 33: | Line 33: | ||
=={{header|C}}== |
=={{header|C}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
{{libheader|GMP}} |
|||
===Basic=== |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 39: | Line 39: | ||
#include <string.h> |
#include <string.h> |
||
#include <stdint.h> |
#include <stdint.h> |
||
#include <gmp.h> |
|||
bool isPrime(uint64_t n) { |
|||
if (n < 2) return false; |
|||
if (n%2 == 0) return n == 2; |
|||
if (n%3 == 0) return n == 3; |
|||
uint64_t d = 5; |
|||
while (d*d <= n) { |
|||
if (n%d == 0) return false; |
|||
d += 2; |
|||
if (n%d == 0) return false; |
|||
d += 4; |
|||
} |
|||
return true; |
|||
} |
|||
bool *sieve(int limit) { |
bool *sieve(int limit) { |
||
Line 74: | Line 61: | ||
return c; |
return c; |
||
} |
} |
||
const char *ord(int count) { |
|||
return (count == 1) ? "st" : |
|||
(count == 2) ? "nd" : |
|||
(count == 3) ? "rd" : "th"; |
|||
} |
|||
int main() { |
int main() { |
||
bool *c = sieve( |
bool *c = sieve(12000); |
||
char sw[ |
char sw[6000] = ""; |
||
char tmp[20]; |
char tmp[20]; |
||
int |
int count = 0, p = 1, ix = 0, i; |
||
mpz_t n; |
|||
int count = 0, p = 1, i; |
|||
mpz_init(n); |
|||
printf("The known Smarandache-Wellin primes are:\n"); |
|||
while (count < 8) { |
|||
while (c[++p]); |
while (c[++p]); |
||
sprintf(tmp, "%d", p); |
sprintf(tmp, "%d", p); |
||
strcat(sw, tmp); |
strcat(sw, tmp); |
||
mpz_set_str(n, sw, 10); |
|||
if ( |
if (mpz_probab_prime_p(n, 15) > 0) { |
||
count++; |
|||
size_t le = strlen(sw); |
|||
char sws[44]; |
|||
if (le < 5) { |
|||
strcpy(sws, sw); |
|||
} else { |
|||
strncpy(sws, sw, 20); |
|||
strcpy(sws + 20, "..."); |
|||
strncpy(sws + 23, sw + le - 20, 21); |
|||
} |
|||
printf("%2d%s: index %4d digits %4ld last prime %5d -> %s\n", count, ord(count), ix+1, le, p, sws); |
|||
} |
|||
ix++; |
|||
} |
} |
||
printf("The first 3 Smarandache-Wellin primes are:\n"); |
|||
for (i = 0; i < 3; ++i) printf("%d ", swp[i]); |
|||
printf("\n"); |
|||
printf("\nThe first 20 Derived Smarandache-Wellin primes are:\n"); |
|||
int freqs[10] = {0}; |
int freqs[10] = {0}; |
||
uint64_t dswp[3]; |
|||
count = 0; |
count = 0; |
||
p = 1; |
p = 1; |
||
ix = 0; |
|||
while (count < 20) { |
|||
while (c[++p]); |
while (c[++p]); |
||
sprintf(tmp, "%d", p); |
sprintf(tmp, "%d", p); |
||
for (i = 0; i < strlen(tmp); ++i) freqs[tmp[i]-48]++; |
for (i = 0; i < strlen(tmp); ++i) freqs[tmp[i]-48]++; |
||
char dsw[ |
char dsw[40] = ""; |
||
for (i = 0; i < 10; ++i) { |
for (i = 0; i < 10; ++i) { |
||
sprintf(tmp, "%d", freqs[i]); |
sprintf(tmp, "%d", freqs[i]); |
||
strcat(dsw, tmp); |
strcat(dsw, tmp); |
||
} |
} |
||
int |
int idx = -1; |
||
for (i = 0; i < strlen(dsw); ++i) { |
for (i = 0; i < strlen(dsw); ++i) { |
||
if (dsw[i] != '0') { |
if (dsw[i] != '0') { |
||
idx = i; |
|||
break; |
break; |
||
} |
} |
||
} |
} |
||
mpz_set_str(n, dsw + idx, 10); |
|||
if (isPrime(dn)) dswp[count++] = dn; |
|||
} |
|||
printf("\nThe first 3 Derived Smarandache-Wellin primes are:\n"); |
|||
for (i = 0; i < 3; ++i) printf("%ld ", dswp[i]); |
|||
printf("\n"); |
|||
free(c); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The first 3 Smarandache-Wellin primes are: |
|||
2 23 2357 |
|||
The first 3 Derived Smarandache-Wellin primes are: |
|||
4194123321127 547233879626521 547233979727521 |
|||
</pre> |
|||
===Stretch=== |
|||
{{libheader|GMP}} |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <stdbool.h> |
|||
#include <string.h> |
|||
#include <stdint.h> |
|||
#include <gmp.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; |
|||
} |
|||
int main() { |
|||
bool *c = sieve(12000); |
|||
char sw[6000] = ""; |
|||
char tmp[20]; |
|||
int count = 0, p = 1, ix = 0; |
|||
mpz_t n; |
|||
mpz_init(n); |
|||
printf("The 4th to the 8th Smarandache-Wellin primes are:\n"); |
|||
while (count < 8) { |
|||
while (c[++p]); |
|||
sprintf(tmp, "%d", p); |
|||
strcat(sw, tmp); |
|||
mpz_set_str(n, sw, 10); |
|||
if (mpz_probab_prime_p(n, 15) > 0) { |
if (mpz_probab_prime_p(n, 15) > 0) { |
||
count++; |
count++; |
||
printf("%2d%s: index %4d prime %s\n", count, ord(count), ix+1, dsw + idx); |
|||
printf("%dth: index %4d digits %4ld last prime %5d\n", count, ix+1, strlen(sw), p); |
|||
} |
|||
} |
} |
||
ix++; |
ix++; |
||
} |
} |
||
free(c); |
free(c); |
||
Line 188: | Line 131: | ||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
The |
The known Smarandache-Wellin primes are: |
||
1st: index 1 digits 1 last prime 2 -> 2 |
|||
2nd: index 2 digits 2 last prime 3 -> 23 |
|||
3rd: index 4 digits 4 last prime 7 -> 2357 |
|||
4th: index 128 digits 355 last prime 719 -> 23571113171923293137...73677683691701709719 |
|||
5th: index 174 digits 499 last prime 1033 -> 23571113171923293137...10131019102110311033 |
|||
6th: index 342 digits 1171 last prime 2297 -> 23571113171923293137...22732281228722932297 |
|||
7th: index 435 digits 1543 last prime 3037 -> 23571113171923293137...30013011301930233037 |
|||
8th: index 1429 digits 5719 last prime 11927 -> 23571113171923293137...11903119091192311927 |
|||
The first 20 Derived Smarandache-Wellin primes are: |
|||
1st: index 32 prime 4194123321127 |
|||
2nd: index 72 prime 547233879626521 |
|||
3rd: index 73 prime 547233979727521 |
|||
4th: index 134 prime 13672766322929571043 |
|||
5th: index 225 prime 3916856106393739943689 |
|||
6th: index 303 prime 462696313560586013558131 |
|||
7th: index 309 prime 532727113760586013758133 |
|||
8th: index 363 prime 6430314317473636515467149 |
|||
9th: index 462 prime 8734722823685889120488197 |
|||
10th: index 490 prime 9035923128899919621189209 |
|||
11th: index 495 prime 9036023329699969621389211 |
|||
12th: index 522 prime 9337023533410210710923191219 |
|||
13th: index 538 prime 94374237357103109113243102223 |
|||
14th: index 624 prime 117416265406198131121272110263 |
|||
15th: index 721 prime 141459282456260193137317129313 |
|||
16th: index 738 prime 144466284461264224139325131317 |
|||
17th: index 790 prime 156483290479273277162351153339 |
|||
18th: index 852 prime 164518312512286294233375158359 |
|||
19th: index 1087 prime 208614364610327343341589284471 |
|||
20th: index 1188 prime 229667386663354357356628334581 |
|||
</pre> |
</pre> |
||