I'm currently learning C and I just created a simple program to find prime numbers :

#include <iostream>
using namespace std;
main() {


// VARIABLES

int num = 3;
int divisor = 2;
const int max = 1000000;
bool prime = true;

// BOUCLE

while (num <= max) {
    while (divisor <= (num / 2)) {
        if ( (num % divisor) == 0) {
            prime = false;
            divisor = 2;
            break;
        }
        divisor  ;
    }
    if (prime == true) {
        cout << num << endl;
    }
prime = true;
num  ;
}
}

My question is about the divisor integer : if the number tested is not prime, the "divisor = 2" line is never executed, so how is my loop working fine? Example : 11 is tested. 11 is a prime number, so the if statement is never executed, but the int divisor value is now 5. Then 12 is tested, starting with the divisor 5. This should cause an error, no?

CodePudding user response：

The reason this works is number theory: you're testing all the even numbers too, and that will always reset your divisor down to 2, ready to do the next test on an odd number (which may or may not be prime).

So let's go past 11 and 12, and go to 13. Your loop will break out of that with a divisor value of 7 and (correctly) mark 13 as prime. Then it'll increment num to 14, and that test will go into your prime=false; section, resetting divisor to 2. Bottom of the loop, testing for 15 now. And the divisor was reset to 2 and you're good, since your code will cycle through 3 as the divisor and 15 will be marked as non-prime (correctly). Then 16 will reset divisor again, ready for 17. Etc.

If you were more clever and only testing odds (if it was num =2 not num at the end), then this case would actually break, since 7 is above the largest factor of 15, and would erroneously say prime. But because you are testing even numbers, and at worst divisor will be half of the number, it'll get reset.

CodePudding user response：

When you find a composite number, you reset divisor to 2, so that's not a problem.
(It is very unclear why you believe that line isn't executed – is that a typo?)

When you find a prime, the next num is going to be even, and the first divisor you test is num / 2 (when you're "done" with 11, the first divisor is 6, not 5).

And since num is even, num / 2 divides num (if a divides b, then so does b/a).

CodePudding user response：

how is my loop working fine?

Code only resets the initial divisor to 2 when a non-prime is found, but not when a prime is found.

    // When true, `num` is _not a prime.
    if ( (num % divisor) == 0) {
        prime = false;
        divisor = 2;
        break;
    }

Normally the divisor = 2; should happen before each new num.

Since code is incrementing, after a prime is found the next num is even and that eventually (num % divisor) == 0 is true. Thus resetting things properly.

A better prime test for reference.

  while (num <= max) {
    // Set first divisor here
    int divisor = 2;
    prime = true;
    // Iterate to the sqrt, not num/2 --> much faster
    while (divisor <= num / divisor) {
      if (num % divisor == 0) {
        prime = false;
        break;
      }
      divisor  ;
    }
    if (prime && num > 3) {
      cout << num << endl;
    }
    num  ;
  }