p357/src/erasto.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

const MAX_PRIMES = 100010000;
const SQRT_MAX_PRIMES = 10000;

int main(int argc, char* argv[]) {
    bool* primes = calloc(MAX_PRIMES, sizeof(bool));
    memset(primes, true, MAX_PRIMES);


    primes[0] = false;
    primes[1] = false;

    for( int i = 2 ; i < SQRT_MAX_PRIMES ; i++) {
        if(primes[i]) {
            for( int j = i*i ; j < MAX_PRIMES ; j+=i) {
                primes[j] = false;
            }
        }
    }

    size_t cnt = 0;
    for( int i = 0 ; i < MAX_PRIMES ; i++)
        if(primes[i]) cnt++;
    printf("Count is : %zu\n", cnt);
}