You can drop every even number from the table, just integer divide by 2 to store the odd numbers only. sum works with booleans mapping them to ints: True is 1 and False is 0; notice that this works even without 2 in table for n >= 2 because 1 is marked as a prime in the table ;)
def n_primes(n):
""" Returns the number of primes < n """
sieve = [True] * (n//2)
for i in xrange(3,int(n**0.5) + 1,2):
if sieve[i//2]:
sieve[i*i//2::i]=[False]*((n-i*i-1)/(2*i)+1)
return sum(sieve)
or even better, count the primes encountered:
def n_primes(n):
""" Returns the number of primes < n (for n > 2)"""
n_p = 1 # 2 is a prime
sieve = [True] * (n//2)
for i in xrange(3,int(n**0.5) + 1,2):
if sieve[i//2]:
n_p += 1
sieve[i*i//2::i]=[False]*((n-i*i-1)/(2*i)+1)
return n_p
Notice, that your sieve function does not return a list but a generator, that yields the result, you probably wanted to write the original code as
def primes(n):
""" Returns a list of primes < n """
sieve = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2] + [i for i in xrange(3,n,2) if sieve[i]]
or using my generator version:
def primes(n):
""" Yields a sequence of primes < n """
if n <= 2:
return
yield 2
sieve = [True] * (n//2)
for i in xrange(3,int(n**0.5) + 1,2):
if sieve[i//2]:
yield i
sieve[i*i//2::i] = [False] * ((n-i*i-1)/(2*i)+1)
In the case of the first, you can do len(primes(n)) to get the number (though this is wasteful), for the second do sum(1 for i in primes(n))
As for generating prime numbers above 100000000, the sieve table would spend (4 * n / 2) bytes on 32-bit processor and 8 * n / 2 on 64-bit processor, so your mileage might vary... One would want to use some kind of bitarray though one is not built-in in python.
