<div>
Given an integer n, return the number of prime numbers that are strictly less than n.
Example 1:
<pre>Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. </pre>
Example 2:
<pre>Input: n = 0 Output: 0 </pre>
Example 3:
<pre>Input: n = 1 Output: 0 </pre>
Constraints:
0 <= n <= 5 * 10<sup>6</sup>
</div>
题目大意：
求n内的素数个数
解题思路：
排除法：知道一个素数后删除它的倍数，剩下的就是下一个素数
解题步骤：
N/A
初始方法
Python代码：
1
2
3
4
5
6
7
8
9
10def countPrimes(self, n: int) -> int:
if n < 2:
return 0
primes = [True] * n # remember less than n
primes[0] = primes[1] = False
for i in range(2, int(math.sqrt(n)) + 1):
if primes[i]:
for j in range(i * i, n, i): # starting from i rather than 2
primes[j] = False
return sum(primes)
注意事项：
- 开一个prime大小数组，初始值为True表示是素数。这样可以遍历到n开方+1. 是最主要的优化步骤，可以优化90%。
- 提高效率：i遍历到n开方+1，删除的数不能超过n(一开始写没有break导致TLE), 最后用sum统计比for循环效率高点
- 删除数字从i * i开始而不是i * 2,因为很多重复计算如2x3与3x2。此时第二个优化步骤。优化15%
- 用数组记录primes而不是set，第三个优化步骤。优化2%
- 题目要求素数小于n，所以不含n
Python代码：
1
2
3
4
5
6
7
8
9
10def countPrimes(self, n: int) -> int:
if n < 2:
return 0
primes = [True] * n # remember less than n
primes[0] = primes[1] = False
for i in range(2, int(math.sqrt(n)) + 1):
if primes[i]:
for j in range(i * i, n, i): # starting from i rather than 2
primes[j] = False
return sum(primes)
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
