You can stop checking for factors after this number because a composite number will always have a factor less than or equal to its square root. To answer the original question, n**0.5 is the same as the square of root of n.
X += 2 # Increment to the next odd number If n % x = 0: return False # A factor was found, so number is not prime # Check odd numbers less than the square root for possible factors # Case 3: the number is odd (could be prime or not) 'Returns True if n is prime, False if n is not prime. Side note 2: primality testing is an interesting problem in computer science. 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.
It tests every number between 2 and n**0.5 including all even and all odd numbers.It does not test if n is less than 2, and there are no primes less than 2.Now, let's look at the algorithm you have: def isPrime(n): 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! 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. The line r = int(n**0.5) evaluates to 70 (the square root of 5003 is 70.7318881411 and int() truncates this value)Ĭonsider the next odd number (since all even numbers other than 2 are not prime) of 5005, same thing prints: 5 not divisible by 3 (with n%3) then we can test every 6th n ± 1.Ĭonsider the prime number 5003: print is_prime(5003).While f 3 are of the form 6n ± 1, once we eliminate that n is:
Of many prime number tests floating around the Internet, consider the following Python function: def is_prime(n):
0 kommentar(er)
