Python sqrt() doubles runtime?
Question: I've recently started learning Python. My apologies if this is really obvious.

I am following along with the 2008 MIT open course on Computer Science and am
working on the problem of calculating the 1000th prime integer. Python 2.7.3,
Win7 lappy (cough, cough...)

Here's the code I came up with:

    
    
    num = 3
    primeList = [2]
    
    while len(primeList) < 1000:
        for i in primeList:
            if num % i == 0:
                break
        else:
            primeList.append(num)
        num += 1
    
    print "The 1,000th PRIME integer is", primeList[999]
    

One of the assignment conditions was to only check odd numbers. Given the
starting `num` is three, I figured it would be easy enough to simply change
`num+=1` to `num+=2`. Of note: I won't bore you with the detailed code I
composed, but while writing this I was using a very verbose mode of printing
out the results of each check, whether or not it was prime, which number was
being checked, which integer divided into it if it wasn't prime & such (again,
sorry - newB!)

At this point I became curious to test if this was actually taking less time
to compute - seemed like if half the numbers are being checked for primacy, it
should take half the time, no?

I imported the time module to check how long this was taking. Computing to the
1000th was pretty quick either way so I increased the number of primes I was
searching for to the 10,000th and didn't see any significant difference.
between `num+=1` & `num+=2`

    
    
    import time
    start = time.time()
    
    num = 3
    primeList = [2]
    
    while len(primeList) < 10000:
        for i in primeList:
            if num % i == 0:
                break
        else:
            primeList.append(num)
        num += 2
    
    print "The 10,000th PRIME integer is", primeList[9999]
    end = time.time()
    print "That took %.3f seconds" % (end-start)
    

Sometimes the `n+=2` even took a couple milliseconds longer. ?. I thought this
was odd and was wondering if someone could help me understand why - or, more
to the point: how?

Furthermore, I next imported the sqrt() function thinking this would reduce
the number of integers being checked before confirming primacy, but this
doubled the runtime =^O.

    
    
    import time
    start = time.time()
    
    from math import sqrt
    
    num = 3
    primeList = [2]
    
    while len(primeList) < 100000:
        for i in primeList:
            if i <= sqrt(num):
                if num % i == 0:
                    break
        else:
            primeList.append(num)
        num += 2
    
    print "The 100,000th PRIME integer is",primeList[99999]
    end = time.time()
    print 'that took', end - start, "seconds, or", (end-start)/60, "minutes"
    

Certainly - it might be the way I've written my code! If not, I'm curious what
exactly I am invoking here that is taking so long?

Thank you!


Answer: Two things.

First, you're calculating `sqrt(n)` on every loop iteration. This will add
work, because it's something else your code now has to do on every pass
through the loop.

Second, the way you're using `sqrt` doesn't reduce the number of numbers it
checks, because you don't exit the loop even when `i` is bigger than
`sqrt(n)`. So it keeps doing a do-nothing loop for all the higher numbers.

Try this instead:

    
    
    while len(primeList) < 100000:
        rootN = sqrt(num)
        for i in primeList:
            if i <= rootN:
                if num % i == 0:
                    break
            else:
                primeList.append(num)
                break
        else:
            primeList.append(num)
        num += 2
    

This finds 100,000 primes in about 3 seconds on my machine.

