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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <inttypes.h>


int frequency_of_primes(int max) {
	if (max < 2) {
		return 0;
	}

	uint64_t *numbers = (uint64_t *)calloc(max/128+1, sizeof(uint64_t));

	uint64_t limit = sqrt(max);
	uint64_t m;
	for (m = 3; m <= limit; m += 2) {
		if (((numbers[m>>7]>>((m>>1) & 63))&1) == 0) {
			int t = m * m;
			while (t <= max) {
				numbers[t>>7] |= (uint64_t)1 << ((t >> 1) & 63);
				t += 2 * m;
			}
		}
	}

	//printf("%ld\n", (uint64_t)2);
	int counter = 1;
	limit = (max+1)/2 - 1;
	for (m = 1; m <= limit; m++) {
		if (((numbers[m>>6]>>(m & 63))&1) == 0) {
			counter++;
			//printf("%ld\n", 2*m+1);
		}
	}

	free(numbers);
	return counter;
}

int main() {
	int f, t;
	int max = 1e9;

	t = clock();
	printf ("Calculating SIEVE...\n");
	f = frequency_of_primes(max);
	t = clock() - t;
	printf ("The number of primes up to %d is: %d (time taken: %f sec)\n", max, f, ((float)t)/(float)CLOCKS_PER_SEC);

	return 0;
}