## Prime Numbers In Python

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 |

Posted by Aaron Toponce on Wednesday, September 5, 2007, at 2:41 pm. Filed under Python.
You can post a comment or trackback from your blog.
For IM, Email or Microblogs, here is the Shortlink.
## { 30 } Comments