Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- int main(int argc, char const *argv[]) {
- if (argc != 2) {
- printf("Usage: sieve N, where N is the desired maximum value for the sieve.\n");
- return -1;
- }
- int N = (unsigned long long) strtoull(argv[1], NULL, 10);
- // Stop sieve at sqrt of max # in sieve, because all non-primes are
- // already gone.
- int M = (int) sqrt((double) N);
- if (N < 0) {
- printf("N must be positive.\n");
- return -1;
- }
- if (N < 2) {
- printf("No primes.\n");
- return 0;
- }
- int * primes;
- primes = calloc(N, sizeof(int));
- // 0 is untouched, 1 is not prime
- printf("2\n");
- for (int i = 3; i <= M; i=i+2) {
- if (primes[i] == 1) continue;
- printf("%d\n", i);
- for (int j = i * i; j <= N; j=j+i) {
- if (primes[j] == 1) continue;
- primes[j] = 1;
- }
- }
- if (!(M % 2)) M = M + 1;
- for (int i = M; i <= N; i=i+2) {
- if (primes[i] == 0) {
- printf("%d\n", i);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement