leetcode/204_count_primes.py at master · sn1572/leetcode · GitHub

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
30
31
32
33
34
35
36
37
38
39
class Solution(object):
    def countPrimes(self, n, *args):
        """
        :type n: int
        :rtype: int
        """

        if n <= 2:
            return(0)
        sieve = dict(zip(range(2,n), (n-2)*[0]))
        index = 2
        while index**2 <= n:
            try:
                sieve[index]
                for j in range(index, n//index+1):
                    try:
                        del sieve[index*j]
                    except:
                        pass
            except:
                pass
            index += 1
        try:
            if args[0]:
                return(sieve)
        except:
            pass
        return(len(sieve.keys()))


if __name__ == '__main__':
    sol = Solution()
    assert(sol.countPrimes(4) == 2)
    assert(sol.countPrimes(5) == 2)
    assert(sol.countPrimes(6) == 3)
    assert(sol.countPrimes(10) == 4)
    assert(sol.countPrimes(11) == 4)
    assert(sol.countPrimes(12) == 5)
    assert(sol.countPrimes(10000) == 1229)