CalmoSoft primes: Difference between revisions
→{{header|C}}: Updated in line with Wren entry of which it is a translation.
(→Stretch: Updated notes) |
(→{{header|C}}: Updated in line with Wren entry of which it is a translation.) |
||
Line 187:
=={{header|C}}==
Run time is 310 milliseconds (GCC -O1) which is slightly slower than Go.
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>
#include <locale.h>
#define MAX 50000000
typedef uint64_t u64;
bool isPrime(u64 n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
while (d*d <= n) {
if (n%d == 0) return false;
Line 205 ⟶ 213:
}
int *primeSieve(int limit, int *length) {
int
int
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) {
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) {
if (i > 0) sum -= primes[i-1];
sum2 = sum;
for (j = pc - 1; j >= i; --j) {
temp = j - i + 1;
if (temp < longest) break;
if (temp > longest) {
longest = temp;
}
sIndices[
eIndices[
sums[
++
break;
}
}
}
*ilen = ic;
return longest;
}
int main() {
int i, j, k, len, ilen, limit, longest;
int *primes = primeSieve(MAX, &len);
int limits[6] = {100, 250, 5000, 10000, 500000, 50000000};
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;
}</syntaxhighlight>
Line 244 ⟶ 321:
{{out}}
<pre>
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 +
</pre>
| |||