筛选法优化b.cpp

来自「素数筛选b算法源程序!输出一个数内所有的素数,此算法是上一算法的优化~主要用VC」· C++ 代码 · 共 50 行

 /*   素数筛选法B 
      崔恒
   */

#include <iostream.h>
#include <math.h>
#define n 10000000001
bool prime[n];

void main()
{
	int i,j,x,q,k;
	cout<<"优化算法B,请输入一个数:";
	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;

    for(i=0; 2*i+3<=sqrt(x); 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;
		 }
		
	}
	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++;
		}
    }

}