diff options
Diffstat (limited to 'count_primes.py')
-rw-r--r-- | count_primes.py | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/count_primes.py b/count_primes.py new file mode 100644 index 0000000..e0d496a --- /dev/null +++ b/count_primes.py @@ -0,0 +1,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)) |