How do you check if a number is prime quickly python?

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`

martineau

115k25 gold badges160 silver badges284 bronze badges

asked Oct 20, 2017 at 3:24

9

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.

answered Oct 20, 2017 at 7:42

Yves DaoustYves Daoust

55.3k8 gold badges43 silver badges99 bronze badges

0

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

answered Oct 20, 2017 at 3:56

Xero SmithXero Smith

1,9181 gold badge13 silver badges19 bronze badges

1

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

oguz ismail

40.7k12 gold badges43 silver badges64 bronze badges

answered Oct 20, 2017 at 5:48

5

How do you check if a number is prime quickly?

How do you check if a number is prime in Python using while loop?