多线程下解决最大约数个数问题的源代码
#include<iostream> #include<windows.h> #include<time.h> using namespace std; //声明素数表的数组为全局变量 int a[10000]={2,0};//素数表初始化 int flagnumber=0;//记录素数表中的个数 int minnumber=0; int maxnumber=0; //一般来说需要声明将要调用的函数 int Simple_count(int a,int b);//累除法 int numlist(int a[])//建立素数表 { int flag=0;//确定数组当前存储素数的位置 bool repeat=true;//循环标志位设定 int j=0; for(int i=2;i<10000;i++)//将通过设定i的上限来扩大搜索的范围 { while(repeat) { if((j==flag)&&(i%a[flag]!=0))//判断是否已经到了当前素数表的最后一个元素,还不能整除的,把当前数字推入素数表 { repeat=false; flag++; a[flag]=i; } else { if(i%a[j]==0)//如果能整除跳出while语句 { repeat=false; } else//否则继续判断 { j++; } } } repeat=true;//i每进行一次测试前,必须置值为真 j=0;//下一个数的除数应该从a[0]开始,所以j应该置零 } return flag;//返回计算的个数 //其实有可能出现误差,如果这个含有最大约数的数还有一个很大的素数因子没有检测出来 //又或者有一个数由于其素数公因子太多,因此少计算进去,可能存在误差 //但是从另一方面考虑,如果这个数真的含有最多的约数,那么它的素数公因子必须很小 //因此,出错的概率必须和a和b之间存在的个数有关 } DWORD WINAPI test(LPVOID pParam) { int jump=0; *((int*)pParam)=jump; bool repeat=true; int testnumber=minnumber;//存储含有最大约数的数,以备检查(利用累除法检查) int numberflag=0;//设置比较位 int statist=1;//到底应该设置统计值为多少需要分析 int b[10000]={0};//初始化当前标志位记载有多少个这样相同的素数,并且初始化 int j=0;//保存指向标志位数组的当前光标 int temp=0;//循环除法的载体 for(int i=jump;i<=maxnumber;i=i+2) { //j不能否超越flag的存在 for( j=0;i>=a[j];j++)//不能超过素数表的界限,但是必须排除这个数小于10000,当这个数很小时,没有必要比较下去 { if(j>flagnumber)//当超出素数表的范围就表示已经遍历完素数表的所有的元素 { break; } else { temp=i; while(temp%a[j]==0)//如果能够整除,标志位加1,同时记得除去已经添加的次数 { b[j]++; //记住a和b的下标是对应的 temp=temp/a[j]; } } } //现在统计这个数含有的公因子个数 for(int k=0;k<=j;k++) { if(b[k]!=0) { statist=statist*(b[k]+1); } } if(numberflag<statist)//取其中最大的数字 { numberflag=statist; testnumber=i; } statist=1;//重置 for( k=0;k<=j;k++) { b[k]=0; } } cout<<"使用素数表的方法获得的最大约数个数是:"<<numberflag<<endl; jump=numberflag; return 0; } int Simple_count(int a,int b)//当a和b之间的个数在50左右时,可以直接使用类除法(通过计算测试时间表明 {//当a的值大于100000000时,每计算一个数,需要花费接近1s的时间,意昧着:计算10万个数需要半小时 int number=0;//统计约数的个数 int flag=0;//设置比较数,当后一个数的约数个数大于前一个数时,重置 for(int i=a;i<=b;i++)//外层循环从a到b { for(int j=1;j<=i/2;j=j+1)//内层循环检测从2到自身 { if(i%j==0) { number++; } } number++;//自身也是一个约数,需添加进去 if(number>flag)//重置标志位 { flag=number; } number=0;//刚才忘记恢复计数值为0 } return flag; } int main() { clock_t start,finish; start=clock(); HANDLE hHandle[2]; int handleresult1,handleresult2; flagnumber=numlist(a);//获得当前的素数表,还有当前素数表的个数flag+1,表示当前素数表从0开始 cout<<flagnumber<<endl; cout<<a[1000]<<endl; int result;//获取当前的结果 cout<<"请输入两个数,以便获取当前的范围"; cout<<endl; cin>>minnumber>>maxnumber; handleresult1=minnumber; handleresult2=minnumber+1; if(maxnumber-minnumber<50) { result=Simple_count(minnumber,maxnumber); } else { hHandle[0]=CreateThread(NULL,0, test,(void*)(&handleresult1),0,NULL); hHandle[1]=CreateThread(NULL,0, test,(void*)(&handleresult2),0,NULL); } WaitForMultipleObjects(2,hHandle,TRUE,INFINITE); finish=clock(); cout<<"the time has been used :"<<finish-start<<endl; return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。