Skip to Content

Count prime numbers - Sieve of Eratosthenes

Home | Coding Interviews | Math | Count prime numbers - Sieve of Eratosthenes

Given an integer n, return the number of prime numbers that are strictly less than n.

class Solution:
    def countPrimes(self, n: int) -> int:
        seen, ans = [0] * n, 0
        for num in range(2, n):
            if seen[num]: continue
            ans += 1
            seen[num*num:n:num] = [1] * ((n - 1) // num - num + 1)
        return ans

Posted by Jamie Meyer 3 months ago

Related Problems