View Single Post
Old 2019-10-16, 11:34   #12
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

There are some improvements to Fermat's method.
See https://en.wikipedia.org/wiki/Fermat...ization_method -> Sieve improvement.
You can really cut down the candidates to check by applying a modulo argument. For primes this argument can be applied multiple times.
For each mod prime number argument it halves the number of numbers "x" to check.
The product of the first 52 primes is ~ 10^98.
Since you can not store or iterate efficiently over all the possible candidates you can not do this for the first 52 primes, you might only seedup by using the first - lets say 8 - primes which gives a speedup of 2^8 = 256.

Also checking if the number is a square can be speed up by applying a mod argument.
Doing it for a power of 2 filters out most of the number to check.

Last fiddled with by ThiloHarich on 2019-10-16 at 12:09
ThiloHarich is offline   Reply With Quote