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