你好,游客 登录 注册 搜索
背景:
阅读新闻

素数验证算法——直面大数据

[日期:2015-04-07] 来源:博客园  作者:Darksun2010 [字体: ]

      素数的验证,可能会被作为所谓“循环练习”的题目。因为其算法实在太简单(不知道直接暴力循环能不能算一种算法)。经典的方法就是试除,用循环变量i从2 开始到n-1,如果有取模为0的,就直接return false。到最后,还没有模出0,就return true。这个算法也可以优化n-1为sqrt(n)。原理是:设x为大于sqrt(n)的数,n=xy,则y一定小于sqrt(n),所以只要验证到 sqrt(n),就能验证到y,相当于验证到了x。

      以上这种暴力算法,如果有N个数要验证,则时间复杂度为O(sqrt(N)*N),面对类似于N=100000000的数据明显力不从心。所以,我们可以 使用筛选法:依次剔除2、3、5、7等素数的倍数,最后就能得出一张素数表。建表后,查询素数只要O(1)的时间复杂度。但是对于以上数量级的N,仍然不 能很快的求出一张素数表,消耗时间高达2.1s。所以,我们还要加以优化。

      众所周知,除去2以外,所有的偶数均为合数。所以,素数表内可以除去偶数。即prime[0]代表3是否为素数,prime[1]代表5……而且,筛数也 不必筛到N,只要筛到sqrt(N)即可。设key1(i)=i*2+3;key2(i)=(i-3)/2,这分别对应素数表内第i个位置表示的奇数与奇 数i在素数表内的存储位置。原来筛的时候,i*(2,3,4…)简化为了i*(3,5,7…)。头一次筛掉的数为key2(key1(i*i)),简化后 为(i*i)*8+3,之后每次累加的数为key2(key1(i+2))-key2(key1(i)),简化后为i*2+3,这样推导完成以后,程序就 很容易写了。下面给出源代码:

复制代码
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;

const int N=100000001;
const int N1=(N-3)/2;
bool prime[N1+1];
int tmp;

int main(void){
    memset(prime,true,sizeof(prime));
    for (int i=0;i<(int(sqrt(N))-3)>>1;++i){
        if (prime[i]){
            tmp=((i*i)<<3)+3;
            while (tmp<N1){
                prime[tmp]=false;
                tmp+=(i<<1)+3;
            }
        }
    }
    printf("%d\t",2);
    for (int i=0;i<N1;++i)
        if (prime[i])   printf("%d\t",i*2+3);
    return 0;
}
复制代码

      附上各种方法的时间与内存占用统计表(测试环境:MinGw4.9.2,Intel Xeon E3 1230V2,去除IO输出时间):

  时间 内存
暴力试除法 N/A(太长了) 1Mb
朴素筛选法 2.1s 98Mb
优化后的筛选法 1.0s 50Mb




收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (3)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款