#
 # Unoptimized Prime Number Calculator
 # (C) 2007 Kevin Mehall
 # BSD License
 # 
 # Read the associated tutorial at http://blog.kevinmehall.net/2007/finding-prime-numbers-1
 #


import math

def is_prime_1(n):
    "Returns whether n is prime or not"
    for i in xrange(2, n):
        if n%i==0: return False
    return True # No factors found
    

def is_prime_2(n):
    "Returns whether n is prime or not"
    for i in xrange(2, int(math.sqrt(n))):
        if n%i==0: return False
    return True # No factors found
    
def test(fn):
	for i in xrange(2, 20000):
		fn(i)
		
import timeit
t=timeit.Timer('test(is_prime_1)', "from __main__ import test, is_prime_1")
print "is_prime_1:"
print t.timeit(1)

t=timeit.Timer('test(is_prime_2)', "from __main__ import test, is_prime_2")
print "is_prime_2:"
print t.timeit(1)