Prime algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isPrime(unsigned long n) {
    if (n <= 3) {
        return n > 1;
    }
 
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
 
    for (unsigned short i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
 
    return true;
}



can anyone explain me how that last part(for loop) works?
Why i is added 2? Is that necessary? I don't understand that algorithm.

Thanks in advance!
Last edited on
Basically, all prime numbers except 2 and 3 can be described as 6 (+-) 1
Since it starts with 5, (which is 6-1), it needs to check 2 higher for the next possible prime, (5+2 = 6+1).

Since if a number A can be divided on a number B, and B can be divided on C, then A must also be able to be divided on C. Therefore there is only a need of checking the C numbers, ie. only primes. Therefor it returns false (n is not a prime) if it's divisible on one of those numbers
I got this! Thanks a million #ITR :) :)
Topic archived. No new replies allowed.