首页 > 代码库 > 关于素数的快速查找——素数筛选法
关于素数的快速查找——素数筛选法
利用素数筛选法进行素数的快速查找。
原理很简单，素数一定是奇数，素数的倍数一定不是素数。
思路如下：
预定义N表示10000，即表示查找10000以内的素数，首先定义数组prime[]对N以内的数进行标记，奇数存为1，偶数存为0，最终实现结果为素数的prime值为1，因此将prime[2]赋值为1（2是素数）。之后利用for循环，对N以内的奇数进行遍历（注意for循环的条件控制），for里用if判断是否为素数（奇数），若是，执行内部嵌套的for循环判断该奇数是否为素数，若是则标记为1，若不是则prime置为0，之后再用if判断是否为素数，若是，则利用循环将该素数的倍数，都标记为0，意在体现，素数的倍数一定不是素数，注意for循环内部的条件：for(j=2*i;j<N;j+=i)，表示遍历i的倍数，j为i的倍数，这是for循环的一个技巧。之后遍历输出prime[i]值为1的i值，便达到了素数的筛选法。
代码如下，利用c语言实现：
#include<stdio.h>
#include<math.h>
#define N 10000
int prime[N];
int main()
{
int i,j,k;
for(i=2;i<=N;i++)
{
if(i&1) prime[i]=1;//奇数存为1
else prime[i]=0;//偶数存为0
}
prime[2]=1;//2是素数
for(i=3;i<N;i+=2)//i+=2 i始终为奇数 在奇数中寻找素数
{
if(prime[i]) //i为素数则执行
{
for(k=2;k<=sqrt(i);k++)
if(i%k==0)
prime[i]=0;//判断i是否为素数 如果i不是素数则存为0
if(prime[i]) //i为素数时
{
for(j=2*i;j<N;j+=i)//i的倍数都不为素数
prime[j]=0;//i的倍数存为0
}//执行完后如果i是素数则prime[i]为1
}
}
for(i=2;i<N;i++)
{
if(prime[i]) printf("%d ",i);
}
getch();
return 0;
}
这一算法理解之后较为简单，主要难点在于for循环的应用，条件的判断，逻辑必须要清晰！
关于素数的快速查找——素数筛选法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。