LeetCode 204 Count Primes

LeetCode

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

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

Constraints:

`0 <= n <= 5 10<sup>6</sup>`

题目大意：

求n内的素数个数

解题思路：

排除法：知道一个素数后删除它的倍数，剩下的就是下一个素数

解题步骤：

N/A

注意事项：

1. 开一个prime大小数组，初始值为True表示是素数。
2. 题目要求素数小于n，所以不含n
3. 提高效率：i遍历到n开方+1，删除的数不能超过n(一开始写没有break导致TLE), 最后用sum统计比for循环效率高点

Python代码：

def 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 * 2, n, i): # starting from i rather than 2
				primes[j] = False
	return sum(primes)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)