62 - 计数质数
题目
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
解答
最直观的解法,就是把所有质数算出来,数一下。
厄拉多塞筛法
作者:magicalchao 链接:https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-bao-li-fa-ji-you-hua-shai-fa-ji-you/
每计算一个数,都要把它的倍数去掉。到了n,数一下留下了几个数。
var countPrimes = function (n) {
let count = 0
signs = []
for (let i = 2; i < n; i++) {
if (!signs[i]) {
count++
for (let j = 2 * i; j < n; j += i) {
signs[j] = true
}
}
}
return count
};
Runtime: 136 ms, faster than 66.06% of JavaScript online submissions for Count Primes.
Memory Usage: 135.7 MB, less than 13.33% of JavaScript online submissions for Count Primes.
signs是用来记录“已经找过的数的倍数”的。
在里面的j循环中,一个个把找过数的倍数,对应的sign,设置为true。这样外循环就不会进入if循环,也就不会计数了。
外面的i循环是用来计数的,只要signs的数是false,就是质数,count就++
由于js里面判断!signs[i]
,啥都没有也是false,因此就不用像题解那样规定好数组一共有几个位置了。
js的优化
经过@Aaron大佬的提点,signs的时候规定好数组的大小,能减少内存的使用
我猜js和go一样,超过了规定的容量,就会把多增加的容量翻倍,倒不如事先规定好要用多少
var countPrimes = function (n) {
...
signs = new Array(n + 1)
...
};
Runtime: 92 ms, faster than 93.73% of JavaScript online submissions for Count Primes.
Memory Usage: 57.9 MB, less than 86.67% of JavaScript online submissions for Count Primes.
天翻地覆的改变👌
go
func countPrimes(n int) int {
count := 0
signs := make([]bool, n)
for i := 2; i < n; i++ {
if signs[i] {
continue
}
count++
for j := 2 * i; j < n; j += i {
signs[j] = true
}
}
return count
}
Runtime: 8 ms, faster than 88.62% of Go online submissions for Count Primes.
Memory Usage: 5 MB, less than 100.00% of Go online submissions forCount Primes.
go就不能这么偷懒了,必须说明新建的这个切片是什么类型,有多少个位置。
go的bool,默认为false。因此如果是true就能直接拿来判断。
Last updated
Was this helpful?