import time
import math

def run_orig(numPrimesToFind):
    x = 3
    counter = 1
    primes = [2]

    while counter < numPrimesToFind:
        if x%2 != 0:
            # code that runs if x is odd
            # this block determines if x is not prime
            for i in range(2, x):
                notPrime = False
                if x%i == 0:
                    # if this code is being run we know that the number is not prime
                    # create a not prime variable and make it true
                    notPrime = True
                    break
            if notPrime == False: #the notPrime variable is false, the number is prime:
                primes.append(x)
                counter += 1
            x += 1
        else:
            #code that runs if x is even
            x += 1

    last = primes.pop(-1)
    return last

def run_new(numPrimesToFind):
    x = 3
    numPrimesFound = 1
    primes = [2]

    while numPrimesFound < numPrimesToFind:
        isPrime = True
        max = math.ceil(math.sqrt(x))
        for i in primes:
            if i > max:
                break
            if x % i == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(x)
            numPrimesFound += 1
        x += 2

    last = primes[-1]
    return last

def getAvgPerf(primeNum, numTrials, function):
    totalTime = 0
    for trial in range(numTrials):
        start = time.time()
        result = function(primeNum)
        elapsed = time.time() - start
        totalTime += elapsed
        print "Test %d/%d took %2.3fs" % (trial + 1, numTrials, elapsed)
    print "Average: %2.3fs" % (totalTime / numTrials)
    return totalTime / numTrials, result

def perfTest(primeNum, numTrials):
    origElapsed, expected = getAvgPerf(primeNum, numTrials, run_orig)
    newElapsed, actual = getAvgPerf(primeNum, numTrials, run_new)
    if expected != actual:
        print "ERROR!!! Functions do not return same value"
    speedIncrease = (1 / newElapsed - 1 / origElapsed) * origElapsed
    print "run_new is %2.3f%% faster" % (speedIncrease * 100)
#perfTest(1000, 10)