(idea) by Olathe Mon Jun 16 2003 at 11:50:41

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 :

  • A = f1 × f2 × … × fn
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.

I like it!