Count Primes

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

# Code

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

tmp = [True] * n

for i in range(2, n):
if(tmp[i]):
for j in range(i*i, n, i):
tmp[j] = False

ret = 0
for i in range(2, n):
if tmp[i]:
ret += 1

return ret
``````
• full code
``````import math
class Solution:
def countPrimes(self, n):
if n <= 1:
return 0

tmp = [True] * n

# i的倍数都是合数
# 逆向思维
for i in range(2, n):
# 可以有效避免重复计算
if(tmp[i]):
for j in range(i*i, n, i):
tmp[j] = False
#从头开始计算
ret = 0
for i in range(2, n):
if tmp[i]:
ret += 1

return ret

# def isPrime(self,x):
#     for i in range(2, int(math.sqrt(x))+1):
#         if (x % i == 0):
#             return False
#     return True

S = Solution()
# print("********************************")
# print(S.countPrimes(10))
print(S.countPrimes(1500000))
``````

### 要不赞赏一下?

 微信 支付宝 PayPal Bitcoin

``https://www.emperinter.info/2022/03/31/count-primes/``

 阿里云国际版 20美元 Vultr 10美元 搬瓦工 | Bandwagon 应该有折扣吧？ Just My Socks JMS9272283 【注意手动复制去跳转】 域名 | namesilo `emperinter`(1美元) 币安 币安