Given an integer n, return the number of prime numbers that are strictly less than n.
Solution
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))