关于快速寻找素数的方法

左手的ㄟ右手 2022-07-12 10:29 181阅读 0赞

利用素数筛选法进行素数的快速查找。

原理很简单，素数一定是奇数，素数的倍数一定不是素数。

思路如下：

预定义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值，便达到了素数的筛选法。

这一算法理解之后较为简单，主要难点在于for循环的应用，条件的判断，逻辑必须要清晰！

#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;
    }