小规模素数表的构造方法及相关

时间：2015-03-01 11:54:38 阅读：307 评论：0 收藏：0 [点我收藏+]

可以写一个判断素数的谓词函数，即从2开始枚举到sqrt(x)(包括)。但这里参数x不能过大，过大就会因为i*i乘积过大溢出。

Code：

后面的内容都是基于这个函数。

//构造素数表
int cnt=0;
int prime[n+1];
for(int i=2;i<=n;++i)
  if(is_prime(i))  prime[cnt++]=i;

这样的话，prime 数组存储的是从 2 开始的素数序列。

int isp[n];
for(int i=2;i<=m;++i)
  isp[i]=is_prime(i);

这样的话，isp 数组保存的是布尔值，即查表 isp[i] 就可以得到数 i 是否为素数。
这个相当于一个预处理，在可能需要判断多个数时，用于不重复调用谓词函数加快速度。

原文：http://blog.csdn.net/buxizhizhou530/article/details/44001777

踩

(0)

评论一句话评论（0）

分享档案

更多>