Algorithm to check prime

Answer 1

For all positive values in the range 0 to infinity:

1. If the value is less than 2 then it is non-prime.

2. If the value is even, then it is prime if and only if the value is 2 otherwise it is non-prime.

3. For all other values, if the value can be divided by any prime factor in the half-closed range 3 to the integer of the square root of the value plus 1, such that the prime factor is less than the value, then it is non-prime, otherwise it is prime.

Note that prime factors are always prime so 2 is therefore a prime factor. But 2 can only be a prime factor of an even number, and we eliminated all even values in step 2. Thus when we reach step 3 we know that the value must be greater than 2 and must be odd. Therefore we only need to check for prime factors greater than 2. The first prime after 2 is 3, therefore we start checking from 3.

The end of the range of prime factors is defined as the integer of the square root of the value plus 1. This is because there's no point in testing higher prime factors because if one existed, there must also be a lower prime factor. E.g., 3*5 is 15 but so is 5*3. If 3 is a factor then we can stop checking. If the value were 17, then 3 would not be a factor. But the next prime factor is 5 which is greater than the square root of 17. If a higher factor than 5 existed then it follows that 3 would also be a factor. So if there are no factors below the square root there can be no factors above the square root. The square root itself could be a factor (as is the case with 25), thus we add 1 to create a half-closed range. That is, the start of the range is 3 and all potential factors must be greater than or equal to 3 but must be less than the upper bound. Checking if a value is less than another is quicker than checking if it is less than or equal to another, so the overhead of adding 1 to the upper bound saves time when there are two or more potential factors to test, which in the majority of cases there will be.

If the upper bound is less than or equal to 3, then there can be no prime factors. If the value were 3 then the range of prime factors would be 3 to 2 and 2 is less than 3 so there are no prime factors therefore 3 is prime. For values 5 and 7, the range becomes 3 to 3. 3 is not less than 3 so there are no prime factors thus 5 and 7 are prime. For all odd values greater than 7, the range becomes valid. Thus a value of 9 creates a range of 3 to 4. 3 is a prime factor of 9 thus 9 is not prime. We can stop checking as soon as we find a prime factor.

For 11 and 13, the range is also 3 to 4. 3 is not a prime factor so we move onto the next prime factor. The simplest way to find the next prime factor is to add 2, because all prime factors must be odd. So the next prime factor is 5. But 5 is not less than 4, the upper bound, so neither 11 or 13 have any prime factors and are therefore odd.

For 15, the range is also 3 to 4 but 3 is a prime factor of 15 so 15 is not prime.

For 17 and 19, the range is now 3 to 5. 3 is not a factor and 5 (the next prime) is not less than 5 (the upper bound), so 17 and 19 are prime.

For 21 (range 3 to 5), 3 is a factor so 21 is not prime.

For 23 (range 3 to 5), 3 is not a factor so 23 is prime.

For 25 (range 3 to 6), 3 is not a factor but 5 is, so 25 not prime.

For 27 (range 3 to 6), 3 is a factor so 27 is not prime.

For 29 (range 3 to 6), neither 3 nor 5 is a factor so 29 is prime.

And so on...