Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

sieve_erastothenes_C

By: a guest on Jul 23rd, 2013  |  syntax: None  |  size: 1.12 KB  |  views: 30  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
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
  14.     // already gone.
  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. }