The big trick here is to avoid the quadratic complexity, and despite
intuition we can do that even with a nested loop (a friend of mine, who is
studying a Msc in Computer Science, reminded me that it does not matter how
many loops you nest; what matters for time complexity is how many times you
process the elements).
What I recall from Sieve of Eratosthenes, is that you checked sequentially
the numbers; for each one you iterate over its multiples and discard them (
if they are multiples, then they are not primes). At the end of this
procedure, you end up with only prime numbers.
Then, our main loop keeps track of what is next number to check. We use an
array for quickly checking whether a number has been discarded, so we do not
process them more than once. A known result tells that we do not need to
check beyond sqrt(n), in the outer loop; so we leverage that.
Note: my original code did not use the sqrt(n) optimization, because I was
stubborn in not doing a final pass to compute the count; in exchange I was
using a counter to keep track of how many elements I processed so far. But
using the sqrt(n) resulted in shorter and faster code.
from math import sqrt class Solution: def countPrimes(self, n): if n <= 2: return 0 is_prime = [True] * n is_prime = False is_prime = False sn = int(sqrt(n)) + 1 for x in range(2, sn): if is_prime[x]: k = 2 while True: fx = k * x if fx >= n: break is_prime[fx] = False k += 1 return sum(is_prime)