Sieve of Pritchard: Difference between revisions
m
→{{minor code polishing}}
Line 203:
#include <ctime>
void Extend (uint32_t w[], uint32_t &w_end, uint32_t &length, uint32_t n
w[++w_end] = x; /* Append x to the ordered set W */\▼
d[x] = false;\▼
▲void Extend (uint32_t w[], uint32_t &w_end, uint32_t &length, uint32_t n, uint32_t N, bool d[], uint32_t &w_end_max) {
/* Rolls full wheel W up to n, and sets length=n */
uint32_t i, j, x;
i = 0; j = w_end;
x = length + 1; /* length+w[0] */
while (x <= n) {
x = length + w[++i];
}
length = n; w_end = j;
if (w_end > w_end_max) w_end_max = w_end;
}
Line 238 ⟶ 234:
j = 0;
for (i=1; i <= imax; i++) {
if (!d[w[i]])
}
if (length < N) {
Line 275 ⟶ 269:
if (length < N) {
/* Extend W with length to minimum of p*length and N: */
Extend (w, w_end, length, std::min(p*length,N)
}
Delete(w, length, p, d, imaxf);
Line 286 ⟶ 280:
if (length < N) {
/* Extend full wheel W,length to N: */
Extend (w, w_end, length
}
/* gather remaining primes: */
Line 323 ⟶ 317:
int stop_s=clock();
printf("\n%d primes up to %lu found in %.3f ms using array w[%d]\n", nrPrimes,
(unsigned long)N, (stop_s-start_s)*
}</syntaxhighlight>
{{out}}
<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149
35 primes up to 150 found in 0.
</pre>
|