Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
这道题目是算有多少个质数在一个范围内，做法不难。
但穷举的解法会超时。
比较好的做法是Sieve of Eratosthenes：Sieve of Eratosthenes - Wikipedia
时间复杂度为 O(n log log n)，空间复杂度为 O(n)
我之前在面试的时候时间复杂度没回答正确。。。。
Python解法如下：
class Solution:
def countPrimes(self, n: int) -> int:
if n < 3:
return 0
primes = [True]*n
primes[0], primes[1] = False,False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
for j in range(i*i,n,i):
primes[j]=False
return sum(primes)
文档信息
- 本文作者：last2win
- 本文链接：https://last2win.com/2020/02/14/LeetCode-204.-Count-Primes/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）