-
Notifications
You must be signed in to change notification settings - Fork 1
/
Primes1.c
72 lines (64 loc) · 1.72 KB
/
Primes1.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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
#include<string.h>
#include<math.h>
/* C99
* ULLONG_MAX +18 446 744 073 709 551 615 - but it clearly goes wild before
* heap size, physical memory size etc.
* from there turtles all the way down - tricks, bits or special libraries..
*/
#define MAX_N 4000000000
static bool * getPrimes(uint64_t n, uint64_t half) {
bool * primes = (bool *)malloc(half * sizeof(bool));
uint64_t i, j, sq, index;
memset(primes, 1, half * sizeof(bool));
sq = (uint64_t)(sqrt(n) +1);
for(i = 3; i < sq; i += 2) {
index = (uint64_t)(i/2);
if(primes[index] == true) {
for(j = (uint64_t) (i * i / 2); j < half; j += i) {
primes[j] = false;
}
}
}
return primes;
}
/* Effective sieve algorithm - generating primes */
int main(int argc, char* argv[]) {
bool * p, * temp;
uint64_t i, N, Half;
N = atoi(argv[1]);
if (N > MAX_N) {
N = MAX_N;
printf("Maximum allowed N is %ld Turtles all the way down.\n", MAX_N);
}
Half = (uint64_t)(N / 2);
p = (bool*)malloc(N * sizeof(bool));
memset(p, 0, N * sizeof(bool));
temp = getPrimes(N, Half);
for(i=1; i < Half; i++) {
if ( temp[i] == true) {
p[2*i+1] = true;
}
}
free(temp);
if ( N < 1000) {
for(i=1; i < N; i++) {
if( p[i] == true)
printf("%llu ", i);
}
} else {
for(i=1; i < 100; i++) {
if(p[i] == true)
printf("%llu ", i);
}
printf("... ");
for(i=N-1; i > N-100; i--) {
if(p[i] == true)
printf("%llu ", i);
}
}
free(p);
return 0;
}