First of all, I am fairly new to C, and know nothing about C , and only took the w3schools.org tutorial on C, and made a few practice programs. What I am looking for is something simple that can find all primes form 1 to 1000000 in under half an hour. I do not know how to implement anything complex like Sieve of Atkin or other complex algorithms. Can you either explain Sieve of Atkin either simpler (like in laymen's terms) or demonstrate it in C? Please keep in mind that I just took the beginner course in C from w3schools.

The code that I am using is as follows:

#include <stdio.h>

int n = 0, i, b, e, flag = 0;

int main() {
    printf("Enter a positive integer that will be the higher bound: ");
    scanf("%d", &b);

    for (n = 0; n < b; n  ) {
        if (n == 0 || n == 1) {
        flag = 1;
        }
      for (i = 2; i <= n / 2;   i) {
        if (n % i == 0) {
          flag = 1;
        }
      }
      if (flag == 0) {
        printf("%d is a prime number.\n", n);
        } else {
        }
        flag = 0;
    }
  return 0;
}

CodePudding user response：

OP's code limits factor testing with for (i = 2; i <= n / 2; i) { - a modest first step.

Yet past the square root of n , there are no factors. Since the root is smaller (usually) , than n/2, this is much quicker.

We could use test_factor * test_factor <= n, but test_factor * test_factor may overflow. Use test_factor <= n/test_factor. Smart compilers will see the nearby n/test_factor and n%test_factor and emit code that executes about as fast as just one of those.

Code could calculate int limit = sqrt(n), but that 1) has edge case problems as sqrt() may no return exactly the sought after root even when it is a whole number 2) may lose needed precession when the integer type has more precision that double. 3) Incurs a floating point cost vs. the nearly no additional cost of test_factor <= n/test_factor.

OP's code sets a flag when a factor is found and then continues to look for more. Yet there is no reason to continue looking. This speeds things up a lot to quit the loop once a factor is found.

We could also check every other value as numbers divided by 2 are not prime - with one exception: 2. This is a modest improvement.

bool is_prime(int n) {
  if (n % 2 == 0) {
    return n == 2;
  }
  for (int test_factor = 3; test_factor <= n / test_factor; test_factor  = 2) {
    if (n % test_factor == 0) {
      return false;
    }
  }
  return n > 1;  // No factors and n is more than 1.
}

Use

for (n = 2; n < b; n  ) {
  if (is_prime(n)) {
    printf("%d is a prime number.\n", n);
  }
}

Note: less than 2 seconds to print all the primes less than 1000000.

For a sieve approach. See Sieve of Eratosthenes pseudo code.