Fastest way of testing if a number is prime?
Solution 1
Exhaustive division until the square root is about the simplest you can think of. Its worst case is for primes, as all divisions must be performed. Anyway, until a billion, there is virtually no measurable time (about 1.2 ms for 1000000007
).
def Prime(n):
if n & 1 == 0:
return 2
d= 3
while d * d <= n:
if n % d == 0:
return d
d= d + 2
return 0
Note that this version returns the smallest divisor or 0
rather than a boolean.
Some micro-optimizations are possible (such as using a table of increments), but I don' think they can yield large gains.
There are much more sophisticated and faster methods available, but I am not sure they are worth the fuss for such small n
.
Solution 2
Here is what I came up with
def is_prime(number):
# if number is equal to or less than 1, return False
if number <= 1:
return False
for x in range(2, number):
# if number is divisble by x, return False
if not number % x:
return False
return True
Solution 3
Primality tests is a very tricky topic.
Before attempting to speed up your code, try to make sure it works as intended. I suggest you start out with very simple algorithms, then build from there.
Of interest, isPrime2 is flawed. It returns True for 6, 10, 12, ...
lines 3 to 6 are very telling
while d*d <= number:
while (number % d) == 0:
number //= d
d += 1
When a factor of number
d is found, number is updated to number = number // d
and at the end of the while loop, if number > 1 you return True
Working through the code with number = 6
:
isPrime2(6)
initialise> number := 6
initialise> d := 2
line3> check (2 * 2 < 6) :True
line4> check (6 % 2 == 0) :True
line5> update (number := 6//2) -> number = 3
line6> update (d : d + 1) -> d = 3
jump to line3
line3> check (3 * 3 < 3) :False -> GOTO line7
line7> check(number > 1) -> check(3 > 1) :True
line8> return True -> 6 is prime
numersoz
Updated on June 05, 2022Comments
-
numersoz almost 2 years
I'm trying to get a fast way to determine if a number is prime using Python.
I have two functions to do this. Both return either True or False.
Function isPrime1 is very fast to return False is a number is not a prime. For example with a big number. But it is slow in testing True for big prime numbers.
Function isPrime2 is faster in returning True for prime numbers. But if a number is big and it is not prime, it takes too long to return a value. First function works better with that.
How can I come up with a solution that could quickly return False for a big number that is not prime and would work fast with a big number that is prime?
def isPrime1(number): #Works well with big numbers that are not prime state = True if number <= 0: state = False return state else: for i in range(2,number): if number % i == 0: state = False break return state def isPrime2(number): #Works well with big numbers that are prime d = 2 while d*d <= number: while (number % d) == 0: number //= d d += 1 if number > 1: return True else: return False`
-
Ry- over 6 years
-
Mark Ransom over 6 yearsUse a Bloom filter that is pre-initialized with a list of prime numbers up to the largest you need to consider.
-
alvas over 6 years
-
Yves Daoust over 6 yearsHow big ? Please be very specific, because the answer will directly depend on that.
-
Yves Daoust over 6 yearsYour first version continues trying all divisors past the square root of
n
, plus uses a hugerange
. It must be banned forever ! Also, trying all even divisors is a pity ! -
Rory Daulton over 6 yearsThere are many posts on this site about fast primality testing in Python. Did you look through them, and why do they not meet your needs?
-
Mark Dickinson over 6 years@RoryDaulton: Not sure that's a good duplicate. Primality testing is an easier problem than full-blown factorization.
-
Mark Dickinson over 6 yearsStill the wrong duplicate. Prime factorization and primality testing are not the same thing. Checking whether a 1000-digit number is (probably) prime is trivially quick; doing a determistic primality check for such a number is slower, but still feasible. But that's way out of the range of effective factorization.
-
-
numersoz over 6 yearsisPrime1 was a function that I wrote, and isPrime2 was something that I modified which was actually intended to calculate Prime Factors of a number. The first function is working, let me work on the second one and fix it. Thanks
-
Xero Smith over 6 yearshaufa. The first line of your function doesn't match the comment. The part `` not number % 2`` will return False for all odd numbers which means it will return False for every prime number except 2. Please modify the function accordingly.
-
numersoz over 6 yearsYour function is faster than my first one. isPrime1(1000000007) gave a result in 70 seconds and is_Prime(1000000007) gave a result in 60 seconds. Its better but lets see what other people have that would work faster.
-
ephrim over 6 years@XeroSmith I've made the changes. Thanks for the correction
-
Yves Daoust almost 5 yearsTesting up to
number
is a total waste. You can stop at√number
. In the case of1000000007
, this is about30000
times faster. -
Hacker over 2 yearsWhy do you only need to go up to the square root