• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# sieve_erastothenes_C

a guest Jul 23rd, 2013 35 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <math.h>
4.
5. int main(int argc, char const *argv[]) {
6.     if (argc != 2) {
7.         printf("Usage: sieve N, where N is the desired maximum value for the sieve.\n");
8.         return -1;
9.     }
10.
11.     int N = (unsigned long long) strtoull(argv[1], NULL, 10);
12.
13.     // Stop sieve at sqrt of max # in sieve, because all non-primes are
15.     int M = (int) sqrt((double) N);
16.
17.     if (N < 0) {
18.         printf("N must be positive.\n");
19.         return -1;
20.     }
21.     if (N < 2) {
22.         printf("No primes.\n");
23.         return 0;
24.     }
25.
26.     int * primes;
27.     primes = calloc(N, sizeof(int));
28.
29.     // 0 is untouched, 1 is not prime
30.     printf("2\n");
31.     for (int i = 3; i <= M; i=i+2) {
32.         if (primes[i] == 1) continue;
33.         printf("%d\n", i);
34.         for (int j = i * i; j <= N; j=j+i) {
35.             if (primes[j] == 1) continue;
36.                 primes[j] = 1;
37.         }
38.     }
39.     if (!(M % 2)) M = M + 1;
40.     for (int i = M; i <= N; i=i+2) {
41.         if (primes[i] == 0) {
42.             printf("%d\n", i);
43.         }
44.     }
45.
46.     return 0;
47. }
RAW Paste Data
Top