opt_prime.cpp

素数筛选算法源程序!主要实现输出一个数内所有的素数~主要用VC实现

/*  素数筛选法
    崔恒 */ 


#include <iostream.h>
                                                                                      
#include <math.h>
                                                                                      
#define n 10000000001
                                                                             
bool prime[n];
                                                                             
void main()
{
	int i,j,x,q,k;
	                                                                                                                               
	cout<<"优化算法A,请输入一个数:";
	                                                                                                                                                                                                       
	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=1;
	                                                                             
		if  (prime[i])
	                                                                             
			k=1;
		                                                                             
		while(j<=q)
		{
		                                                                             
			j=k*(2*i+3)+i;                                                                             
	                                                                             
			k++;                                                                              
	                                                                             
			prime[j]=false;                                                                             
		 }                                                                             
		                                                                             
	}
	                                                                             
	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++;                                                                             
		}                                                                             
                                                                                                                              
	                                                                             
                                                 	                                                                             
	}                                                                             
                                                                             
                                                                             
                                                                             

}