64 lines
1.4 KiB
C
64 lines
1.4 KiB
C
|
#include <assert.h>
|
||
|
|
#include <inttypes.h>
|
||
|
|
#include <stdio.h>
|
||
|
|
#include <stdlib.h>
|
||
|
|
#include <string.h>
|
||
|
|
#include <time.h>
|
||
|
|
|
||
|
|
typedef uint64_t prime_t;
|
||
|
|
|
||
|
|
int main(void) {
|
||
|
|
|
||
|
|
struct timespec ts;
|
||
|
|
double t0, t1;
|
||
|
|
|
||
|
|
clock_gettime(CLOCK_MONOTONIC, &ts);
|
||
|
|
t0 = ts.tv_sec + ts.tv_nsec * 1E-9;
|
||
|
|
|
||
|
|
// Initialize
|
||
|
|
uint8_t *is_prime;
|
||
|
|
prime_t n = 4;
|
||
|
|
|
||
|
|
is_prime = malloc(n);
|
||
|
|
is_prime[0] = 0;
|
||
|
|
is_prime[1] = 0;
|
||
|
|
is_prime[2] = 1;
|
||
|
|
is_prime[3] = 1;
|
||
|
|
|
||
|
|
for (;;) {
|
||
|
|
clock_gettime(CLOCK_MONOTONIC, &ts);
|
||
|
|
t1 = ts.tv_sec + ts.tv_nsec * 1E-9;
|
||
|
|
if (t1 - t0 >= 1.0) break;
|
||
|
|
|
||
|
|
prime_t n1 = n * 2;
|
||
|
|
assert(n1 > n);
|
||
|
|
is_prime = realloc(is_prime, n1);
|
||
|
|
assert(is_prime);
|
||
|
|
memset(is_prime + n, 1, n1 - n);
|
||
|
|
|
||
|
|
for (prime_t i = 2; i < n1; i++) {
|
||
|
|
if (!is_prime[i]) continue;
|
||
|
|
// printf("%ju is prime:", (uintmax_t)i);
|
||
|
|
|
||
|
|
prime_t m = (n + (i - 1)) / i * i;
|
||
|
|
if (m == i) m += i;
|
||
|
|
|
||
|
|
for (; m < n1; m += i) {
|
||
|
|
// printf(" %ju", (uintmax_t)m);
|
||
|
|
is_prime[m] = 0;
|
||
|
|
}
|
||
|
|
// printf("\n");
|
||
|
|
}
|
||
|
|
n = n1;
|
||
|
|
}
|
||
|
|
prime_t n_primes = 0;
|
||
|
|
for (prime_t i = 0; i < n; i++) {
|
||
|
|
if (is_prime[i]) {
|
||
|
|
// printf("%ju\n", (uintmax_t)i);
|
||
|
|
n_primes++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
printf("%ju primes <= %ju in %g seconds\n", (uintmax_t)n_primes, (uintmax_t)n, t1 - t0);
|
||
|
|
|
||
|
|
}
|