204. 计数质数
image-20201203195128240
思路
-
枚举
一般咱们用来判断一个数比如说23是否是质数，我们可以用23除以[2, 23)里面的数字，一旦有数字大于1，该数字肯定就不是质数。
但是每次除以那么多数字，其实可以简化。
想想一下，判断x是否是y的因数（也就是x是否能被y整除）
如果x是y的因素，那么y ÷ x肯定也是y的因数，所以其实只要计算[2, min(y/x, y)]是否能被y整除就行。
那么什么时候y/x最小呢
引用一下题解，感觉比我解释的好:
image-20201203201748756
但是此方法会超时
// 超时警告
func isPrime(x int) bool {
for i := 2; i*i <= x; i++ {
if x%i == 0 {
return false
}
}
return true
}
func countPrimes(n int) (cnt int) {
for i := 2; i < n; i++ {
if isPrime(i) {
cnt++
}
}
return
}
-
埃氏筛
简单的说就是，如果x是质数，那么2x 3x 4x....这些一定不是质数
那么从2开始我们就可以找出2的2倍，3倍，排除这些非质数，一直遍历，看数组里还有哪些质数，数量+1，返回总数即可
所以可以写出如下代码:
func countPrimes(n int) (cnt int) {
// 创建一个bool数组，里面存放第N个数是否是质数
// 初始化，使得每个数都是质数
isPrime := make([]bool, n)
for i := range isPrime {
isPrime[i] = true
}
// 从2开始 2是质数，把数组里2的倍数都刷为素数
for i := 2; i < n; i++ {
if isPrime[i] {
cnt++
for j := 2 * i; j < n; j += i {
isPrime[j] = false
}
}
}
return
}
image-20201203204422642
class Solution:
def countPrimes(self, n: int) -> int:
ans = 0
result = [True for i in range(n)]
for i in range(2, n):
if result[i]:
ans += 1
j = 2 * i
while j < n:
result[j] = False
j += i
return ans
image-20201203204605411
