Advertisement
Guest User

sieve_erastothenes_C

a guest
Jul 23rd, 2013
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement