forked from shichao-an/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsolution.py
More file actions
37 lines (29 loc) · 833 Bytes
/
Copy pathsolution.py
File metadata and controls
37 lines (29 loc) · 833 Bytes
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
"""
Description:
Count the number of prime numbers less than a non-negative number, n.
Hint:
Let's start with a isPrime function. To determine if a number is prime, we
need to check if it is not divisible by any number less than n. The runtime
complexity of isPrime function would be O(n) and hence counting the total
prime numbers up to n would be O(n2). Could we do better?
"""
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
for i in range(2, n):
if self.is_prime(i):
res += 1
return res
def is_prime(self, k):
i = 2
while i * i <= k:
if k % i == 0:
return False
i += 1
return True
s = Solution()
print(s.countPrimes(500))