204 - Count Primes
Written on November 4, 2015
Tweet
Count the number of prime numbers less than a non-negative number, n.
class Solution:
def countPrimes(self, n: int) -> int:
if n < 2:
return 0
dp = [True] * n
dp[0] = dp[1] = False
for i in range(2, int(n ** 0.5) + 1):
if dp[i]:
for j in range(i * i, n, i):
dp[j] = False
return sum(dp)