Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!

# sieve_erastothenes_C

By: a guest on Jul 23rd, 2013  |  syntax: None  |  size: 1.12 KB  |  views: 33  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
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. }
clone this paste RAW Paste Data
Top