# primes – isPrime Function for Python Language

## primes – isPrime Function for Python Language

Of many prime number tests floating around the Internet, consider the following Python function:

``````def is_prime(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
r = int(n**0.5)
# since all primes > 3 are of the form 6n ± 1
# and test f, f+2 for being prime
# then loop by 6.
f = 5
while f <= r:
print(t,f)
if n % f == 0: return False
if n % (f+2) == 0: return False
f += 6
return True
``````

Since all primes > 3 are of the form 6n ± 1, once we eliminate that `n` is:

1. not 2 or 3 (which are prime) and
2. not even (with `n%2`) and
3. not divisible by 3 (with `n%3`) then we can test every 6th n ± 1.

Consider the prime number 5003:

``````print is_prime(5003)
``````

Prints:

`````` 5
11
17
23
29
35
41
47
53
59
65
True
``````

The line `r = int(n**0.5)` evaluates to 70 (the square root of 5003 is 70.7318881411 and `int()` truncates this value)

primes – isPrime Function for Python Language

Consider the next odd number (since all even numbers other than 2 are not prime) of 5005, same thing prints:

`````` 5
False
``````

The limit is the square root since `x*y == y*x` The function only has to go 1 loop to find that 5005 is divisible by 5 and therefore not prime. Since `5 X 1001 == 1001 X 5` (and both are 5005), we do not need to go all the way to 1001 in the loop to know what we know at 5!

Now, lets look at the algorithm you have:

``````def isPrime(n):
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False

return True
``````

There are two issues:

1. It does not test if `n` is less than 2, and there are no primes less than 2;
2. It tests every number between 2 and n**0.5 including all even and all odd numbers. Since every number greater than 2 that is divisible by 2 is not prime, we can speed it up a little by only testing odd numbers greater than 2.

So:

``````def isPrime2(n):
if n==2 or n==3: return True
if n%2==0 or n<2: return False
for i in range(3, int(n**0.5)+1, 2):   # only odd numbers
if n%i==0:
return False

return True
``````

OK — that speeds it up by about 30% (I benchmarked it…)

The algorithm I used `is_prime` is about 2x times faster still, since only every 6th integer is looping through the loop. (Once again, I benchmarked it.)

Side note: x**0.5 is the square root:

``````>>> import math
>>> math.sqrt(100)==100**0.5
True
``````

Side note 2: primality testing is an interesting problem in computer science.

With `n**.5`, you are not squaring n, but taking the square root.

Consider the number 20; the integer factors are 1, 2, 4, 5, 10, and 20. When you divide 20 by 2 and get 10, you know that it is also divisible by 10, without having to check. When you divide it by 4 and get 5, you know it is divisible by both 4 and 5, without having to check for 5.

After reaching this halfway point in the factors, you will have no more numbers to check which you havent already recognized as factors earlier. Therefore, you only need to go halfway to see if something is prime, and this halfway point can be found by taking the numbers square root.

Also, the reason 1 isnt a prime number is because prime numbers are defined as having 2 factors, 1 and itself. i.e 2 is 1*2, 3 is 1*3, 5 is 1*5. But 1 (1*1) only has 1 factor, itself. Therefore, it doesnt meet this definition.

#### primes – isPrime Function for Python Language

The question was asked a bit ago, but I have a shorter solution for you

``````def isNotPrime(Number):
return 2 not in [Number,2**Number%Number]
``````

The math operation will mostly return 2 if the number is a prime, instead of 2. But if 2 is the given number, it is appended to the list where we are looking into.

Examples:

``````2^5=32    32%5=2
2^7=128   128%7=2
2^11=2048 2048%11=2
``````

Counter examples:

``````2^341%341=2,  but 341==11*31
2^561%561=2,  but 561==3*11*17
2^645%645=2,  but 645==3*5*43
``````

isNotPrime() reliably returns True if Number is not prime though.