筛选法优化d.cpp

来自「两次素数筛选算法源程序!先筛选sprt(n)内的素数,再选n内的素数,些算法更快」· C++ 代码 · 共 55 行

#include <iostream.h>
#include <math.h>
#define n 10000000001
bool prime[n];
int i,j,q,k;
void fuck(int p)
{
	
    for(i=0; 2*i+3<=sqrt(p); i++)
	{	
		j=i*(2*i+6)+3;
		k=(j-i)/(2*i+3);
		if  (prime[i])
		
		while(j<=q)
		{
		prime[j]=false;
		k++; 
		j=k*(2*i+3)+i;
		 }
	}
 
}
void main()	
{
	int x,y;
	cout<<"优化算法D,请输入一个数:";
	cin>>x;
    if (x%2==0) q=x/2-2;
    else q=(x+1)/2-2;
	for (i=0;i<=q;i++)
		prime[i]=true;

    y=sqrt(x);
    fuck(y);
	fuck(x);
	cout<<"   "<<x<<"内的所有的素数为:"<<endl<<"2"<<endl; 
    k=1;
	for(i=0;i<=q;i++)	
	{   
       
		if (prime[i]) 
		{
			cout<<i*2+3<<"           ";
			if(k%5 == 0) cout<<endl;
            k++;
		}
		
		
    }

}