The following program returns True if a number is prime or False otherwise. I am proud of this code, as it implements dead code. Upon the first positive condition in the if statement nested in the while loop, the program terminates, ignoring any further code following. As far as I can tell, this is the most efficient way (not necessarily the fastest) to test if a number is prime or not. This means that this function has an order of O(n-2) (it doesn't test against 1 and itself) as a worst case scenario, and O(n/m) where m is the first factor of n as a best case. As elementary as it is, I think it's pretty slick. All handled in 9 very readable lines of code.
UPDATE: Thanks to some observant readers, I have come to the realization that I only need to loop to the square root of n, and not n, as the square root of n is the largest factor. This brings the order to O(sqrt(n)-2) at the worst case scenario, and O(1) as the best case.
1 2 3 4 5 6 7 8 9 | def is_prime(n): import math n = abs(n) i = 2 while i <= math.sqrt(n): if n % i == 0: return False i += 1 return True |
{ 30 } Comments