CalmoSoft primes: Difference between revisions

Content added Content deleted
(→‎Stretch: Updated notes)
(→‎{{header|C}}: Updated in line with Wren entry of which it is a translation.)
Line 187: Line 187:


=={{header|C}}==
=={{header|C}}==
Run time is 310 milliseconds (GCC -O1) which is slightly slower than Go.
<syntaxhighlight lang="c">#include <stdio.h>
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdbool.h>
#include <string.h>
#include <string.h>
#include <stdint.h>
#include <locale.h>


#define MAX 50000000
bool isPrime(int n) {

typedef uint64_t u64;

bool isPrime(u64 n) {
if (n < 2) return false;
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
if (n%3 == 0) return n == 3;
int d = 5;
u64 d = 5;
while (d*d <= n) {
while (d*d <= n) {
if (n%d == 0) return false;
if (n%d == 0) return false;
Line 205: Line 213:
}
}


int *primeSieve(int limit, int *length) {
int main() {
int primes[30] = {2}, sIndices[5], eIndices[5], sums[5];
int i, p, *primes;
int i, j, k, temp, sum, si, ei, pc = 1, longest = 0, count = 0;
int j, pc = 0;
limit++;
for (i = 3; i < 100; i += 2) {
// True denotes composite, false denotes prime.
if (isPrime(i)) primes[pc++] = i;
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) {
u64 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;
}
}
for (i = 0; i < limit; ++i) {
if (!c[i]) ++pc;
}
primes = (int *)malloc(pc * sizeof(u64));
for (i = 0, j = 0; i < limit; ++i) {
if (!c[i]) primes[j++] = i;
}
free(c);
*length = pc;
return primes;
}

int calmoPrimes(int limit, int *primes, int len, int *sIndices, int *eIndices, u64 *sums, int *ilen) {
int i, j, temp, pc = len, longest = 0, ic = 0;
u64 sum = 0, sum2;
if (limit < MAX) {
for (i = 0; i < len; ++i) {
if (primes[i] > limit) {
pc = i;
break;
}
}
}
}
for (i = 0; i < pc; ++i) sum += primes[i];
for (i = 0; i < pc; ++i) {
for (i = 0; i < pc; ++i) {
for (j = pc-1; j >= i; --j) {
if (pc - i < longest) break;
if (i > 0) sum -= primes[i-1];
sum2 = sum;
for (j = pc - 1; j >= i; --j) {
temp = j - i + 1;
temp = j - i + 1;
if (temp < longest) break;
if (temp < longest) break;
sum = 0;
if (j < pc - 1) sum2 -= primes[j+1];
for (k = i; k <= j; ++k) sum += primes[k];
if (isPrime(sum2)) {
if (isPrime(sum)) {
if (temp > longest) {
if (temp > longest) {
longest = temp;
longest = temp;
count = 0;
ic = 0;
}
}
sIndices[count] = i;
sIndices[ic] = i;
eIndices[count] = j;
eIndices[ic] = j;
sums[count] = sum;
sums[ic] = sum2;
++count;
++ic;
break;
break;
}
}
}
}
}
}
*ilen = ic;
printf("The longest sequence(s) of CalmoSoft primes having a length of %d is/are:\n\n", longest);
return longest;
for (i = 0; i < count; ++i) {
}
si = sIndices[i];

ei = eIndices[i];
int main() {
sum = sums[i];
int i, j, k, len, ilen, limit, longest;
for (j = si; j <= ei; ++j) printf("%d + ", primes[j]);
int *primes = primeSieve(MAX, &len);
printf("\b\b= %d which is prime\n", sum);
int limits[6] = {100, 250, 5000, 10000, 500000, 50000000};
if (i < count - 1) printf("\n");
setlocale(LC_NUMERIC, "");
int sIndices[5];
int eIndices[5];
u64 sums[5];
for (i = 0; i < 6; ++i) {
limit = limits[i];
longest = calmoPrimes(limit, primes, len, sIndices, eIndices, sums, &ilen);
printf("For primes up to %'d the longest sequence(s) of CalmoSoft primes\n", limit);
printf("having a length of %'d is/are:\n\n", longest);
for (j = 0; j < ilen; ++j) {
char cps[130] = "";
char buf[20];
int bytes = 0, totalBytes = 0;
for (k = sIndices[j]; k <= sIndices[j]+5; ++k) {
bytes = sprintf(buf, "%d + ", primes[k]);
strcpy(cps + totalBytes, buf);
totalBytes += bytes;
}
strcpy(cps + totalBytes, ".. + ");
totalBytes += 5;
for (k = eIndices[j]-5; k <= eIndices[j]; ++k) {
bytes = sprintf(buf, "%d + ", primes[k]);
strcpy(cps + totalBytes, buf);
totalBytes += bytes;
}
cps[totalBytes-3] = '\0';
printf("%s = %'ld\n", cps, sums[j]);
}
printf("\n");
}
}
free(primes);
return 0;
return 0;
}</syntaxhighlight>
}</syntaxhighlight>
Line 244: Line 321:
{{out}}
{{out}}
<pre>
<pre>
The longest sequence(s) of CalmoSoft primes having a length of 21 is/are:
For primes up to 100 the longest sequence(s) of CalmoSoft primes
having a length of 21 is/are:

7 + 11 + 13 + 17 + 19 + 23 + .. + 67 + 71 + 73 + 79 + 83 + 89 = 953

For primes up to 250 the longest sequence(s) of CalmoSoft primes
having a length of 49 is/are:

11 + 13 + 17 + 19 + 23 + 29 + .. + 223 + 227 + 229 + 233 + 239 + 241 = 5,813

For primes up to 5,000 the longest sequence(s) of CalmoSoft primes
having a length of 665 is/are:

7 + 11 + 13 + 17 + 19 + 23 + .. + 4957 + 4967 + 4969 + 4973 + 4987 + 4993 = 1,543,127

For primes up to 10,000 the longest sequence(s) of CalmoSoft primes
having a length of 1,223 is/are:

3 + 5 + 7 + 11 + 13 + 17 + .. + 9883 + 9887 + 9901 + 9907 + 9923 + 9929 = 5,686,633
7 + 11 + 13 + 17 + 19 + 23 + .. + 9901 + 9907 + 9923 + 9929 + 9931 + 9941 = 5,706,497

For primes up to 500,000 the longest sequence(s) of CalmoSoft primes
having a length of 41,530 is/are:

2 + 3 + 5 + 7 + 11 + 13 + .. + 499787 + 499801 + 499819 + 499853 + 499879 + 499883 = 9,910,236,647

For primes up to 50,000,000 the longest sequence(s) of CalmoSoft primes
having a length of 3,001,117 is/are:


7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 which is prime
7 + 11 + 13 + 17 + 19 + 23 + .. + 49999699 + 49999711 + 49999739 + 49999751 + 49999753 + 49999757 = 72,618,848,632,313
</pre>
</pre>


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