//筛选 0-num的素数
function primes(num) {
var s = [];
//初始化0-num的值
for (var i = 0; i <= num; i++) {
s.push(i);
}
//筛掉不合适的值
delete s[0];
delete s[1];
for (var j = 2; j <= num; j++) {
if (!s[j]) continue;//如果 j 是合数
for (var k = 2; j * k <= num; k++) {
delete s[j * k];//筛掉合数
}
}
//去掉被删掉的值
return s.filter(function(x) {
return x;
})
}
var res = primes(10)
console.log(res);
判断一个数是否为质数 素数筛选法（时间复杂度O(nlogn)）
素数筛选
关于怎么判断一个数 n 是否是质数，最简单的方法是枚举 2 到 n−1，判断是否是 n 的约数。如果是， n 肯定...
题目：实现一个存储正整数的类，此类中的数据用随机数的方式进行填充。提供的方法包括：打印所有的整数、打印数据中所有的...
今天在面试时被问到了一个问题：求不大于n的最大素数，当时只想出暴力解法，回来查资料找到了正确的求解方法。 素数筛法...
直接方案：从1-10000筛选质数时候，正常是遍历所有数字，然后遍历所有比自身小的数，如果除以一个比自身小又不是1...
好久没写博客了。这是一个关于寻找质数的故事。 完全借鉴于 sieve-of-eratosthenes-algori...
素数线性筛选 素数的定义是除了1和自身能被整除外，没有其他数能被它整除。除此之外，1既不是素数，也不是合数。因此，...
区间素数线性筛选 假设应用场景为求一个区间长度远小于右端点的所有素数，该区间为 。如若使用朴素素数线性筛选，则需...
本文标题：筛选素数/筛选质数
本文链接：https://www.haomeiwen.com/subject/tragzxtx.html
网友评论