Aug-11-2023, 09:15 PM
For fun I used ideas from the sympy prime code referenced by DeaD_EyE and re-ran some comparisons based on the algorithms in my previous post. This is my modified is_prime code that uses a small list of known primes (range 2 to 199).
The next prime after 100,000 is 100,003. Calculating all primes between 100,001 and 200,000 in a less than efficient manner performed 1,256,391,701 modulo divisions as opposed to 104 by the algorithm above. On my laptop the runtime was 150 seconds vs too small to measure.
And the inefficiency isn't all due to searching for all primes between x+1 and 2x. I ran a test to compute the next prime for every number in the range 100,001 and 200,000. Using the list of small primes to reduce how many factors are used to test for "primeness", my algorithm only hand to perform 18,000,463 modulo divisions. That looks like a lot, but 18 million is pretty small when compared to 1.25 billion.
def is_prime(x):
global count
if x in small_primes:
return True
nmax = int(x**0.5) + 1
for n in small_primes:
count += 1
if n > nmax:
return True
if x % n == 0:
return False
for n in range(211, nmax, 2):
count += 1
if x % n == 0:
return False
return TrueThe next prime after 10067 is 10069. To calculate this the algorithm posted by FirstBornAlbatross performs 15,733,439 modulo divisions. The algorithm above performs 27.The next prime after 100,000 is 100,003. Calculating all primes between 100,001 and 200,000 in a less than efficient manner performed 1,256,391,701 modulo divisions as opposed to 104 by the algorithm above. On my laptop the runtime was 150 seconds vs too small to measure.
And the inefficiency isn't all due to searching for all primes between x+1 and 2x. I ran a test to compute the next prime for every number in the range 100,001 and 200,000. Using the list of small primes to reduce how many factors are used to test for "primeness", my algorithm only hand to perform 18,000,463 modulo divisions. That looks like a lot, but 18 million is pretty small when compared to 1.25 billion.