isPrime Function for Python Language

Solution 1:

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
  # start with f=5 (which is prime)
  # 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)

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, let's 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.

Solution 2:

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 haven't 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 number's square root.

Also, the reason 1 isn't 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 doesn't meet this definition.