leetcode
leetcode copied to clipboard
204. 计数质数
统计所有小于非负整数 n 的质数的数量。
示例 1:
输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2:
输入:n = 0
输出:0
示例 3:
输入:n = 1
输出:0
提示:
- 0 <= n <= 5 * 106
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/count-primes 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
- 暴力解题 (超时)
const countPrimes = n => {
let nums = []
for (let i = 2; i < n; i++) {
let flag = true
for (let num of nums) {
let res = i / num
if (res === ~~res) {
flag = false
break
}
}
if (flag) nums.push(i)
}
return nums.length
}
- 哈希表
const countPrimes = n => {
let arr = [], count = 0
for (let i = 2; i < n; i++) {
if (!arr[i]) {
for (let j = i * i; j < n; j += i) {
arr[j] = true
}
count++
}
}
return count
}