patternpythonMinor
Python Prime Testing
Viewed 0 times
primetestingpython
Problem
This code seems surprisingly fast at checking if a number is prime.
However, is there any way to speed this prime testing up?
def is_prime(number: int) -> bool:
"""Checks if a number is prime or not"""
# number must be integer
if type(number) != int:
raise TypeError("Non-integers cannot be tested for primality.")
# negatives aren't prime, 0 and 1 aren't prime either
if number <= 1:
return False
# 2 and 3 are prime
elif number <= 3:
return True
# multiples of 2 and 3 aren't prime
elif number % 2 == 0 or number % 3 == 0:
return False
# only need to check if divisible by potential prime numbers
# all prime numbers are of form 6k +/- 1
# only need to check up to square root of number
for i in range(5, int(number**0.5) + 1, 6):
if number % i == 0 or number % (i + 2) == 0:
return False
return TrueHowever, is there any way to speed this prime testing up?
Solution
Congratulations, you just came up with a prime sieve! And indeed, it's faster than always considering all the multiples of 2 of 3. But why do you stop at multiples of 2 and 3? What about 5? And 7? But why stop somewhere?
Let's be more ambitious. What about skipping all the multiples of all the primes encountered so far? This is called the sieve of Eratosthenes. It uses more memory (if you double the maximum number you're interested in, you need twice the memory), but it will be faster and will tell you if any number below your maximum number is prime.
If you want more improvements, note that other prime sieves exist: both the sieve of Sundaram and the sieve of Atkin improve over the sieve of Eratosthenes. And of course, if you're interested in raw speed, use numpy or even a language like C.
Let's be more ambitious. What about skipping all the multiples of all the primes encountered so far? This is called the sieve of Eratosthenes. It uses more memory (if you double the maximum number you're interested in, you need twice the memory), but it will be faster and will tell you if any number below your maximum number is prime.
If you want more improvements, note that other prime sieves exist: both the sieve of Sundaram and the sieve of Atkin improve over the sieve of Eratosthenes. And of course, if you're interested in raw speed, use numpy or even a language like C.
Context
StackExchange Code Review Q#141028, answer score: 3
Revisions (0)
No revisions yet.