Further optimizations :
RolloThomasi's algorithm works by stopping when it finds the smallest prime-factor of A or when it is sure that A is prime. For example, with 1,573,499 (23 × 37 × 43²), it only needs to check until it reaches the smallest prime-factor, which is 23. When is the earliest we can stop checking for prime factors of A, because we are sure that A is prime ? We need to figure out how big the smallest prime-factor (f1) can possibly get.
A non-prime number is equal to all its prime factors multiplied together :
So, using
algebra, we know the smallest prime-factor of
A is :
- f1 × f2 × … × fn = A (same as above, only reversed)
- f1 = A ⁄ (f2 × … × fn)
So, to figure out what the
maximum possible value of
f1 is, we need to figure out what the
minimum possible value of (
f2 × … ×
fn) is. The minimum possible value of (
f2 × … ×
fn) happens when
A has only two
equal prime-factors. For example, 169 has only two equal prime factors (13 and 13). So, we use the following algebra :
- f1 = A ⁄ f2
- f1 = A ⁄ f1 (since f1 = f2)
- f1² = A
- f1 = √A
And, we see that the highest we ever have to check is the
square root of
A, which is almost always lower than half of
A (which is how high
RolloThomasi's program will check). Also, think about what happens when
f2 is greater than
f1 and about what happens when you add in more prime factors; you should find that the highest you have to check actually goes lower than the square root of
A, so by checking up to the square root of
A, you'd be doing all you need to and then some.
You can also further speed things up by eliminating floating-point numbers; if the square root has anything after the decimal point, you can ignore it. If we are checking whether 211 is prime, √211 ≈ 14.526, so we only need to check up to 14.
You can also skip checking against all even numbers, except for two. If the number wasn't divisible by two, it won't be divisible by any other even number. This is fairly easy to do by adding two to B each cycle instead of one (don't forget to check numbers by dividing by two).1
To further enhance the skipping optimization, you can check against only two, three, and all numbers that fit the forms of 6k − 1 and 6k + 1 to further reduce the number of factors to check.
1What I have covered so far can be found in C at the Useful Number Theory functions in C node.