primes - isPrime Function for Python Language

Question

So I was able to solve this problem with a little bit of help from the internet and this is what I got:

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

But my question really is how to do it, but WHY. I understand that 1 is not considered a "prime" number even though it is, and I understand that if it divides by ANYTHING within the range it is automatically not a prime thus the return False statement. but my question is what role does the squar-rooting the "n" play here?

P.s. I am very inexperienced and have just been introduced to programming a month ago.

Answer 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('',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.