Optimal trial division

gistfile1.txt

It is not necessary to check all numbers. In fact, the most common algorithm for determining if a number is prime begins at the number 5 (after checking if the number was 2 or 3), and updates by 6 each iteration, and always checks 2 conditions. 

So far, it has only been proven that we only need check up the square root of the number we're testing, which is the reason for checking all numbers up to that point. If you're interested, below is a common algorithm for testing for primality. 

if(n <= 3)
return n > 1;

else if(n % 2 == 0 || n % 3 == 0)
return false;

for(int i = 5; i * i <= n; i += 6)
if(n % i == 0 || n % (i + 2) == 0)
return false;

return true;

The idea is mostly pretty simple. We take an integer n, and first check if it is less than or equal to 3. If it is, we know the number is prime if it is 2 or 3. The last part, beginning from the for loop, constantly checks two things, beginning from the number 5. 

We know that 5 is a prime number. If we add one, we are guaranteed an even number, which cannot possibly be prime (factor of 2). So, it is unnecessary to add 1. Now, if we add 2, there is nothing to show that the number can't be prime, which is why, during each iteration, we always check if the current number and 2 numbers after that are prime. 

Next, since we started at 5, an odd number, if we add 3, we get to an even number. Again, can't be prime. If we add 4, it turns out the number cannot be prime (I forget the reason for this, and it may be a little more complicated, but it is discussed on various websites). Adding 5 again gives an even number. 

So, what we do is start from 5, always check the current number and 2 above (so 5 and 7 to start), then add 6 to the first number (5 + 6 gives 11). 

So to give the first set of possible numbers, we have 5 and 7, then 11 (5 + 6) and 13, then 17 (11 + 6) and 19, and so on. 

So for every set of 6 numbers, we can skip 4 of them, which means we only need check 33% of all numbers using this approach. 

For example, in the set {5, 6, 7, 8, 9, and 10}, we only check 5 and 7.
In the next set {11, 12, 13, 14, 15, and 16}, we only check 11 and 13. 

To summarize the whole thing, if you are given a number n, we only need check 33% of numbers up to the square root of n. 

Pretty cool huh? 
Hope this helped! :)