The fastest approach should be first to sieve the numbers by marking the numbers divisible by small primes (for this you should use only one long division per short prime), then to use a Fermat test to find a number that the base 2 (as it is very likely more efficient since multiplication with 2 is a primeleft shift) on all unmarked numbers. Finally apply a certain number of Miller-Rabin tests ( to the candidate all candidates passing the Fermat test ) to reduce your error probability to a level you can tolerate (e.g., $2^{-100}).
|
2 | corrected finding a prime to finding all primes | ||
|
|
||||
|
|
1 |
|
||
|
The fastest approach should be first to sieve the numbers by marking the numbers divisible by small primes (for this you should use only one long division per short prime), then to use a Fermat test to find a number that is very likely a prime. Finally apply a certain number of Miller-Rabin tests (to the candidate passing the Fermat test) to reduce your error probability to a level you can tolerate (e.g., $2^{-100}). |
||||
