当前位置: 首页>>数据结构与算法>> 阅读正文

素数判定算法

Category: 数据结构与算法 View: 19,349 Author: Dong

  • 评论 (6)
  • 引用通告 (0)
发表评论 发起引用

  • 1楼satan 回复

    Post: 2012-08-22 01:49

    筛法那块里面的is_primer[4]= is_primer[6]= is_primer[8]= is_primer[10]= 应该是false么、

    [回复]

  • 2楼huozhixinxin 回复

    Post: 2012-08-29 01:47

    楼主的博客挺精致的,很有收获,不够这篇里出现了几个错误:
    1、原始算法与改进算法中的return true,return false 语句错位了。
    2、load_primer_table2()函数中:
    for(i = 1; i <= upper; i++) {
    if(test(i)) {
    for(j = i + i; j < INT_MAX; j += i)
    set(i); //此处错误
    }
    }
    set(i)应该改为clear(j).
    3、1楼说的地方。

    [回复]

  • 3楼huozhixinxin 回复

    Post: 2012-08-29 02:25

    4.load_primer_table2()函数中第一个for循环:
    for(i = 1; i <= INT_MAX; i++) { //此处错误
    if( i % 2) {
    set(i);
    } else {
    clear(i);
    }

    i应该从3开始循环测试的.增加预处理:clear(1),set(2).
    文章似乎认为2是合数。。。所以涉及到出发点的时候都有这个问题。
    不过在最后经过优化后,若在测试函数is_primer3(int i)中增加
    if(1==i) return false;
    if(2==i) return true;
    if(i % 2 == 0) return false;
    int j = i/2-1;
    test(j)即可。位图中对应位置存储的是3,5,7,9…….//存储空间折半

    [回复]

  • 4楼397090770 回复

    Post: 2012-09-25 08:26

    博主不错,不过文章中有些地方可能是笔误,好几处写错了如2楼所说。

    [回复]

  • 5楼shyJohnnie 回复

    Post: 2013-04-06 03:15

    跟楼主分享个素数判定的正则表达式:
    1.首先要将原数写为全1的形式,即2=“11”,7=“1111111”,N即为N个1的子串;
    2.使用这个正则表达式匹配::/^1?$|^(11+?)\1+$/
    不知是哪个GEEK想出来的,真是厉害啊

    [回复]

    shyJohnnie 回复:

    如果跟上个表达式匹配,则必定是非素数,不匹配即素数

    [回复]

  • 6楼hamduke 回复

    Post: 2014-02-28 07:03

    素数很稀疏,即使把 2 – max_int 的所有素数顺序存在内存里面也没多少,用二分法比较岂不更快

    [回复]

目前还没有任何Trackbacks和Pingbacks.
发表评论