test.cpp

一个关于求至少1万以内素数的方法

#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<fstream.h>

//判断两个整数是否互质,认为1和任何整数互质
bool IsPremeNumber(int m,int n)
{
	if(m==1||n==1)return true;
	else
	{
		int temp=0;
		if(m>n)
			temp=n;
		else temp=m;
		for(int i=temp;i>1;i--)
		{
			if(m%i==0&&n%i==0)
				return false;
		}
		return true;

	}
}
//输出由小到大默认C最大
void output(int count,int a,int b,int c,const char *out)
{
//	cout<<a<<" "<<b<<" "<<c<<endl;
//	else cout<<b<<" "<<a<<" "<<c<<"fffff"<<endl;
	ofstream outfile(out,ios::app|ios::out);
  	if(!outfile)
	{
		cout<<"打开输出文件失败！";
		exit(1);
	}
	outfile<<count<<" "<<a<<" "<<b<<" "<<c<<endl;
	outfile.close();
}
//算法设计确定最小数min;
void main(void)
{
	char in[20]="in.txt";
	char out[20]="out.txt";
//读入数值
	int num[1000];
	int ccnum=0;
	ifstream infile(in,ios::in|ios::nocreate);
	if(!infile)
	{
		cout<<"打开输入文件失败！";
		exit(1);
	}
	int readnumber;
	while(infile>>readnumber)
	{
		num[ccnum]=readnumber;
		ccnum++;
	}
 	infile.close();

	int ccount=ccnum; 
	cout<<"需要输出 "<<ccount<<" 个符合要求的勾股数组。"<<endl;
	cout<<"程序运行中，请稍等......"<<endl;

//对数值进行排序
	int atemp[1000],btemp[1000],ctemp[1000];
	int numsort[1000];
	int numtemp[1000];
	int sortnumber=0;
	int sort;
	bool repeat=false;
	for(int i=0;i<ccount;i++)
	{
		atemp[i]=btemp[i]=ctemp[i]=numsort[i]=0;
	}
	for(i=0;i<ccount;i++)
	{
		numtemp[i]=num[i];
	}
	for(i=0;i<ccount;i++)
	{
		for(int j=i+1;j<ccount;j++)
		{
			if(num[i]>num[j])
			{
				sort=num[i];
				num[i]=num[j];
				num[j]=sort;
			}
			else if(num[i]==num[j]) 
			{
				repeat=true;
				break;
			}
		}
		if(repeat==false)
		{
			numsort[sortnumber]=num[i];
			sortnumber++;
		}
		else
			repeat=false;

	}

//计算
	int point=0;
	int count=0;
	int a,b,c;     
	int m,n;
	int m2,n2;
	for(int min=3;min<100000;min++)
	{
		if(min%4==0)
		{
			b=min;
	        int temp=b/2;
	        for(m=2;m<=temp;m++)
			{
			   if((n=temp/m)>m);
		       else if(temp%m==0&&(n=temp/m)<m)
			   {
		         if((m%2==1&&n%2==0)||(m%2==0&&n%2==1))//m为奇数n为偶数||m为偶数n为奇数
				 {
					 m2=m*m;
				     n2=n*n;
				     a=m2-n2;
			         c=m2+n2;
					 if(a>b)
					 {
		    	       if(IsPremeNumber(m,n)==true)
					   {
						 count++;	cout<<count<<"is ok!\n";
						 if(count==numsort[point])
						 {
						  atemp[point]=b;
						  btemp[point]=a; 
						  ctemp[point]=c;
						  point++;
						  if(point==sortnumber)
						  {
							  for(int pp=0;pp<ccount;pp++)
							  {
								  for(int qq=0;qq<sortnumber;qq++)
								  {
									  if(numtemp[pp]==numsort[qq])
									  {
										  output(numtemp[qq],atemp[qq],btemp[qq],ctemp[qq],out);
										  break;
									  }
								  }
							  }
							  exit(1);
						  }
						 }
					 }
				   }//end ispreme
				 }//end jiou
			   }//end temp%m
			}//end for m=2
		}//end min 2k
		else//min=2k+1
		{
			a=min;
			int tempa=(a+1)/2;
			for(m=sqrt(a)+1;m<=tempa;m++)
			{
				int n2=m*m-a;
				int n=sqrt(n2);//完全平方数
				if(n2==n*n)
				{
					b=2*m*n;
					if(a<b)
					{
						if(IsPremeNumber(m,n)==true)
						{
							c=m*m+n2;
							count++;	cout<<count<<"is ok!\n";
							if(count==numsort[point])
							{
								atemp[point]=a;
								btemp[point]=b;
								ctemp[point]=c;
								point++;
								if(point==sortnumber)
								{
									for(int pp=0;pp<ccount;pp++)
									{
										for(int qq=0;qq<sortnumber;qq++)
										{
											if(numtemp[pp]==numsort[qq])
											{
												output(numtemp[qq],atemp[qq],btemp[qq],ctemp[qq],out);
											}
										}
									}
							      exit(1);
								}
							}//end if(count==numsort[point])
						}
					}
				}
			}	
		}
	}//end for min
}