I've written a more powerful version of the Sieve of Eratosthenes, this Sieve returns the number of factors of all the numbers below the limit
.Sadly the running time is \$O(n^2)\$, so it is much slower than the ordinary sieve. Can you suggest a way to improve and optimize it?
import doctest
def factors_sieve(limit):
"""
Returns the number of factors of all the numbers below the limit.
For better convenience use list(enumerate(factors_sieve(limit)))
>>> list(enumerate(factors_sieve(9)))
[(0, 0), (1, 1), (2, 2), (3, 2), (4, 3), (5, 2), (6, 4), (7, 2), (8, 4)]
>>> factors_sieve(100000).count(2) # How many prime numbers below 100000?
9592
"""
sieve = [2]*limit
sieve[0],sieve[1] = 0,1
for number,number_of_divisors in enumerate(sieve):
if number >= 2:
for multiple in range(number*2, len(sieve), number):
sieve[multiple] += 1
return sieve
if __name__ == "__main__":
doctest.testmod()