求任意自然数内的素数 -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> 求任意自然数内的素数

求任意自然数内的素数

浏览:1620次出处信息

用6N±1法求素数

任何一个自然数，总可以表示成为如下的形式之一：

6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)

显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数。所以，除了2和3之外，所有的素数都可以表示成6N±1的形式(N为自然数)。

根据上述分析，我们可以构造另一面筛子，只对形如6 N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度。

以下代码需要自然数大于10

以下是代码片段：
    function fn(num){
    var arr = [];
    arr.push(2);
    arr.push(3);
    arr.push(5);
    arr.push(7);
    var t = 0;
    for (var i = 3; t < num; i = i + 3) {
    for (var j = 0; j < 2; j++) {
    t = 2 * (i + j) - 1;
    if (t < num && (t % 5 == 0 ? false : t % 7 == 0 ? false : true)) {
    arr.push(t);
    }
    }
    }
    return arr.join(” “);
    }
    document.write(fn(1000));

各位大侠有没有更高效的方法或以上代码有不对的地方，请指出。

建议继续学习：

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：算法复杂度求法初学

后一篇：快速排序详细分析 >>

文章信息

作者：mike 来源： 163 UED Team
标签：素数
发布时间：2009-11-16 23:22:42

建议继续学习

近3天十大热文