技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 求任意自然数内的素数

求任意自然数内的素数

浏览:1618次  出处信息

    用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));

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

建议继续学习:

  1. 聊聊如何检测素数    (阅读:2346)
  2. 又一种证明素数无穷多的方法    (阅读:2057)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1