["python","primes"]
isPrime Function for Python Language

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 square-rooting the "n" play here? P.s. I am very inexperienced and have just been introduced to programming a month ago.
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: not 2 or 3 (which are prime) and not even (with n%2) and 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: It does not test if n is less than 2, and there are no primes less than 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.