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

1458 Posts
Default

Has anybody tried the Trial Division algorithm : https://github.com/TilmanNeumann/jav...63Inverse.java ?

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