Tags: "leetcode", "sieve-of-eratosthenes", "prime-number", "hashmap", access_time 1-min read

Edit this post on Github

Count Primes

Created: November 9, 2018 by [lek-tin]

Last updated: November 9, 2018

Count the number of prime numbers less than a non-negative number, n.

Example

Input: 10
Output: 4

Explanation There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Solution

class Solution:
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 2:
            return 0
        marked = [0] * (n-1)
        for i in range(int(n**0.5)+1):
            if marked[i] != 1:
                prime = i + 2
                for j in range(prime**2-2, n-1, prime):
                    marked[j] = 1
        count = 0
        for c, k in enumerate(marked):
            # We are counting numbers less than n, hence len(marked)-1
            if k == 0 and c < len(marked)-1:
                count += 1
        return count

Cleaner version

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 1:
            return 0

        primes = [True for _ in range(n)]
        count = 0
        for i in range(2, n):
            if primes[i]:
                print(i)
                count += 1
                for j in range(2, n):
                    if j * i >= n:
                        break
                    primes[i*j] = False

        return count