Quickly determine if a number is prime in Python for numbers < 1 billion
- by Frór
Hi,
My current algorithm to check the primality of numbers in python is way to slow for numbers between 10 million and 1 billion. I want it to be improved knowing that I will never get numbers bigger than 1 billion.
The context is that I can't get an implementation that is quick enough for solving problem 60 of project Euler: I'm getting the answer to the problem in 75 seconds where I need it in 60 seconds. http://projecteuler.net/index.php?section=problems&id=60
I have very few memory at my disposal so I can't store all the prime numbers below 1 billion.
I'm currently using the standard trial division tuned with 6k±1. Is there anything better than this? Do I already need to get the Rabin-Miller method for numbers that are this large.
primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def isprime(n):
if n <= 100:
return n in primes_under_100
if n % 2 == 0 or n % 3 == 0:
return False
for f in range(5, int(n ** .5), 6):
if n % f == 0 or n % (f + 2) == 0:
return False
return True
How can I improve this algorithm?
