aboutsummaryrefslogtreecommitdiff
path: root/count_primes.py
blob: e0d496aacabb8077150b45efb39473a3acebfe33 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 204. Count Primes

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


class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n**0.5) + 1):
            if primes[i]:
                primes[i * i : n : i] = [False] * len(primes[i * i : n : i])
        return sum(primes)


if __name__ == "__main__":
    obj = Solution()
    print(obj.countPrimes(10))
    print(obj.countPrimes(1))
    print(obj.countPrimes(0))