Search code examples
primespseudocode

prime numbers algorithm efficiency

I have a question about prime numbers algorithm.

why in the following pseudo code i increases by 6 and not by 2 every iteration?

function is_prime(n)
if n ≤ 1
    return false
else if n ≤ 3
    return true
else if n mod 2 = 0 or n mod 3 = 0
    return false
let i ← 5
while i * i ≤ n
    if n mod i = 0 or n mod (i + 2) = 0
        return false
    i ← i + 6
return true

Thanks!

Solution

  • If it increased by 2 it would be testing almost everything twice, that wouldn't make any sense. So I assume you mean: how can it get away with not testing every odd number?

    This is because every prime p greater than 3 is of the form 6n±1. Proof: Consider the remainder r = p mod 6. Obviously r must be odd. Notice also that r cannot be 3, because then p would be divisible by 3, making it not a prime. This leaves only the possibilities 1 and 5, which correspond p being of the form 6n+1 or the form 6n-1 respectively.

    The effect is that it avoid testing multiples of 3. Dividing by a multiple of 3 is redundant, because we already know that n is not a multiple of 3, so it cannot be the multiple of a multiple of 3 either.