View Single Post
Old 2019-01-21, 08:04   #23
ThiloHarich's Avatar
Nov 2005

1458 Posts

Has anybody tried the Trial Division algorithm : ?

The idea is pretty simple:
Since we anyway compute a list of primes, why not also calculate the inverse of the prime as a double value and store it as well. Then instead of doing a trial division with this prime we multiply with its reciprocal. We have to check if this value is an integer. So we convert the value to long and see if this multiplied by the prime gives the back the original number to test.

We observed a reasonable speedup over standard trial division.
ThiloHarich is offline   Reply With Quote