prime numbers

[deanhystad]

This is best described using an example. Lets say we want to determine if 36 is prime. It is not, really not. 36 has a lot of factors.
2 x 18
3 x 12
4 x 9
6 x 6 <- square root of 36
9 x 4
12 x 3
18 x 2

Notice that the factors below the square root are just swapped versions of factors above the square root. This is because of the Commutative property of multiplication which says "a x b = b x a". If we were testing for prime, we wouldn't have to test 18, because we already tested for 18 when we tested for 2. We don't have to test 13, because we already tested 13 when we tested 3. The largest number we ever have to test to determine if a number is prime is the square root of the number. Any potential factor greater than the square root has already been tested by the commutative property. Now apply this information to determining if 101 is prime.

To determine if 101 is prime, the largest potential factor we need to test is the square root of 101, 10.05. Round down to 10. Without any kind of optimization, we might test for prime using 2, 3, 4, 5, 6, 7, 8, 9, 10. This is already far better than testing 2 - 100 as potential factors, 10 times fewer divisions. But we can do even better than that.

We can factor some of the remaining potential factors
2
3
4 = 2 x 2
5
6 = 2 x 3
7
8 = 2 x 2 x 2
9 = 3 x 3
10 = 2 x 5

If a number is divisible by 4, 6, 8 or 10 (or any even number) it is also divisible by 2. Thus, any number that has an even factor also has 2 as a factor. This means the only even factor we ever have to test is 2. This cuts the list of potential factors almost in half; 2, 3, 5, 7, 9.

You probably also noticed that 9 can be factored to 3 x 3. For the same reason that any number that is a multiple of 2 (any even number) can be ignored as a potential factor, any number that is a multiple of 3 (or 5 or 7 or any of the other primes) can be ignored as a factor. There is no reason to test if 9 is a factor if you already ruled out that 3 is not a factor. However, it is not as easy to rule out multiples of primes as it is multiples of 2, so we will test if 101 is divisible by 9 and ignore that it is not optimal.

An algorithm to determine if a number is prime must:
1. Have a special test for 2, the only even prime number
2. Have a special test for numbers less than 2, all of which are not prime.
3. Only if the number > 2, test for prime using modulo and factors
a. If the number is divisible by a factor it is not prime.
b. If you tested all factors the number is prime

Step 3 is easily optimized to only test odd factors (read about the range() function).