Faster way to list primes in Python

pythonprimes

def listprimes2(m):
    '''another attempt to list all primes below m'''
    values = range(m+1) #note that in this list the key and the value are the same.
    primes = values[:]
    primes[1] = 0 #1 doesn't count as a prime
    for i in values:
        if primes[i] == 0:
            pass
        else:
            for j in values[i+1:]:
                if primes[j]==0 or primes[j]%i != 0:
                    pass
                else:
                    primes[j] = 0
    return primes

    
import time
tstart = time.time()
ans = sum(listprimes2(2000000))
telapsed = time.time()-tstart

I figured it out! The part I was missing was stopping the iterator at the square root mark. I added this:
sqrt = m**.5
...
for i in values[:int(sqrt)+1]: #update to line 6

It looks like you're creating two arrays populated with the values of their indices, then marking the non-prime entries as zero. You decide whether each number is prime or not by looking at every larger value. Unfortunately, you do this check too many times (see line 10, for j in values[i+1:]:). For example, you will check if the number j = 500 is prime at least 499 times: when i is 1, when i is 2, etc.

So you should instead devise a way that doesn't keep checking the same thing repeatedly.

Additionally, there are some obvious shortcuts you can take to reduce the running time.

• Other than 2, no number divisible by 2 is prime, so you never need to check even numbers.
• Other than 3, no number divisible by 3 is prime, so you don't need to check numbers divisible by 3.
• Other than 5, no number divisible by 5 is prime, so you don't need to check numbers divisible by 5.

Removing multiples of 2, 3, and 5 reduces the set of numbers you must check by about 70%, so you should instantly observe about a 3x speedup.

For a better approach to finding primes quickly, you should check out the Sieve of Eratosthenes, which is an extremely efficient way of finding small prime numbers (< 10 million to 20 million or so) quickly. In fact, if you kept following the bullets outlined above, and continued up to the largest prime that is less than sqrt[2,000,000], that would actually be an equivalent algorithm to the SoE.

It took about 37 seconds to execute. I know it's not perfect, but at least got the right answer.

thanks John!