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('\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.

Answer 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.