5_prime_algorithm_compare.rar_C prime_prime

#include <iostream> #include <bitset> #include <fstream> #include <vector> #include <bitset> #include <ctime> #include <cmath> using namespace std; void Output(ofstream& fOut,vector<int>& vPrime); void Compare(vector<int>& vCompar1,vector<int>& vCompar2); void Check_Proc_Time( void Funtion(vector<int>&,const int) ,const int iSerial,vector<int>& Output,ofstream& fFile,const int N); void Find_All_Prime1(vector<int>& vInt_Prime,const int N); void Find_All_Prime2(vector<int>& vInt_Prime,const int N); void Find_All_Prime3(vector<int>& vInt_Prime,const int N); void Find_All_Prime4(vector<int>& vInt_Prime,const int N); void Find_All_Prime5(vector<int>& vInt_Prime,const int N); class cMy_Bitset; int main() { vector<int> vInt_Prime,vInt_Prime_Original;//初始化 ofstream fOut("素数.txt"); ofstream fOut_Original("素数标准.txt"); const int N = 0000000; typedef void (*FUNTION_POINT)(vector<int>&,const int ); typedef void (*RUN)( void (*)(vector<int>&,const int) ,const int ,vector<int>& ,ofstream &,const int ); vector<FUNTION_POINT> vFuntion; vFuntion.push_back(Find_All_Prime1); vFuntion.push_back(Find_All_Prime2); vFuntion.push_back(Find_All_Prime3); vFuntion.push_back(Find_All_Prime4); vFuntion.push_back(Find_All_Prime5); //Check_Proc_Time(Find_All_Prime1();0,vInt_Prime,N); int x =4; FUNTION_POINT fpTest_Funtion = vFuntion[x-1]; RUN fpRun = Check_Proc_Time; (*fpTest_Funtion)(vInt_Prime,N); (*fpRun)(fpTest_Funtion,x,vInt_Prime_Original,fOut_Original,N); x = 4; fpTest_Funtion = vFuntion[x-1]; fpRun = Check_Proc_Time; (*fpTest_Funtion)(vInt_Prime,N); (*fpRun)(fpTest_Funtion,x,vInt_Prime,fOut,N); /* x = 3; fpTest_Funtion = vFuntion[x-1]; fpRun = Check_Proc_Time; (*fpTest_Funtion)(vInt_Prime,N); (*fpRun)(fpTest_Funtion,x,vInt_Prime_Original,N); x = 4; fpTest_Funtion = vFuntion[x-1]; fpRun = Check_Proc_Time; (*fpTest_Funtion)(vInt_Prime,N); (*fpRun)(fpTest_Funtion,x,vInt_Prime_Original,N); */ cout<<"比较结果:"<<endl; Compare(vInt_Prime_Original,vInt_Prime); cout<<endl; system("pause"); return 0; } //-------------------------------------------------测试时间 void Check_Proc_Time( void Funtion(vector<int>&,const int) ,const int iSerial,vector<int>& iInt_Prime,ofstream& fFile,const int N){ clock_t tStart = clock(); Funtion(iInt_Prime,N); cout<<"Find_ALL_Prime"<<iSerial<<" :time is :"<<clock()-tStart<<"ms"<<endl; cout<<" 数量:"<<iInt_Prime.size()<<endl; Output(fFile,iInt_Prime); } //------------------------------------------输出数据 void Output(ofstream& fOut,vector<int>& vPrime){ for(vector<int>::iterator pFirst = vPrime.begin();pFirst != vPrime.end();++ pFirst){ fOut<<*pFirst<<" "; if((pFirst-vPrime.begin()) %8 == 8-1) fOut<<endl; } return; } //--------------------------------比较两个函数输出结果有什么不同 void Compare(vector<int>& vCompare1,vector<int>& vCompare2){ vector<int> vTemp_Save1,vTemp_Save2; vTemp_Save1.clear(); vTemp_Save2.clear(); for(vector<int>::iterator pFirst = vCompare1.begin(), pSecond = vCompare2.begin();;){ if(pFirst == vCompare1.end()){ cout<<"缺少:"<<" "<<vTemp_Save1.size()<<endl; for(vector<int>::iterator pBegin = vTemp_Save1.begin();pBegin != vTemp_Save1.end() ;++ pBegin){ cout<<*pBegin<<" "; } cout<<endl<<"错误:"<<" "<<vTemp_Save2.size()+vCompare2.end()-pSecond<<endl; for(vector<int>::iterator pBegin = vTemp_Save2.begin();pBegin != vTemp_Save2.end() ;++ pBegin){ cout<<*pBegin<<" "; } for(;pSecond != vCompare2.end() ;++ pSecond){ cout<<*pSecond<<" "; } break; } if(pSecond == vCompare2.end()){ cout<<"缺少:"<<" "<<vTemp_Save1.size()+vCompare1.end()-pFirst<<endl; for(vector<int>::iterator pBegin = vTemp_Save1.begin();pBegin != vTemp_Save1.end() ;++ pBegin){ cout<<*pBegin<<" "; } for(pFirst;pFirst != vCompare1.end() ;++ pFirst){ cout<<*pFirst<<" "; } cout<<endl<<"错误:"<<" "<<vTemp_Save2.size()<<endl; for(vector<int>::iterator pBegin = vTemp_Save2.begin();pBegin != vTemp_Save2.end() ;++ pBegin){ cout<<*pBegin<<" "; } break; } if(*pFirst < *pSecond) vTemp_Save1.push_back(*pFirst ++); if(*pFirst > *pSecond) vTemp_Save2.push_back(*pSecond ++); if(*pFirst == *pSecond){ pFirst ++; pSecond ++; } } } //存放所有的比N小的素数,然后是否能被这些素数整除所有小于N void Find_All_Prime1(vector<int>& vInt_Prime,const int N){ vInt_Prime.clear(); vInt_Prime.resize(1,2); for(int n = 3;n <= N;n += 2){ vector<int>::iterator pFirst = vInt_Prime.begin(); for(;pFirst != vInt_Prime.end();++ pFirst){ if(!(n % *pFirst)) break; } if(pFirst == vInt_Prime.end()) vInt_Prime.push_back(n); } } //存放所有的比N小的素数,然后是否能被那些平方<N的素数的 整除所有小于N void Find_All_Prime2(vector<int>& vInt_Prime,const int N){ vInt_Prime.clear(); vInt_Prime.resize(1,2); vector<int>::iterator pFirst = vInt_Prime.begin(); bool mark = true; for(int n = 3;n <= N;n += 2){ int iTemp = (int)sqrt(n)+1; mark = true; vector<int>::iterator pFirst = vInt_Prime.begin(); for(;*pFirst <iTemp && pFirst != vInt_Prime.end();++ pFirst){ if(!(n % *pFirst)){ mark = false; } } if(mark) vInt_Prime.push_back(n); } } //刷掉的数目是: n^2+2kn (n为素数,k= 0,1,2,3,4.... //转换公式为 n^2 +2kn k为素数,k = 0,1,2,3,... void Find_All_Prime3(vector<int>& vInt_Prime,const int N){ vector<int> vTemp_Prime(N,1); vTemp_Prime[0] = 0; //把1 刷掉 for(int x = 4;x <= vTemp_Prime.size();x += 2) vTemp_Prime[x-1] = 0; bool Mark = false; for(int Start = 3;Start < N ;++ Start){ Mark = false; for(int x = Start;x <vTemp_Prime.size();++ x)//找下一个素数起点 if(vTemp_Prime[x-1]){ Start = x; Mark = true; break; } if(!Mark) break; //是否还有合适的素数起点 if(Start*Start < Start) //溢出处理 刷掉的数据有 n*n+2*i*n //a为素数,i= 0,1,2,3,4,.... break; for(int x = Start * Start; x <= vTemp_Prime.size(); x += Start*2){ vTemp_Prime[x-1] = 0; } } vInt_Prime.clear(); for(vector<int>::iterator pFirst = vTemp_Prime.begin();pFirst != vTemp_Prime.end();++ pFirst){ if(*pFirst) vInt_Prime.push_back(pFirst-vTemp_Prime.begin()+1); } } //z这个和 上一个算法没有什么区别,仅空间省略了一般,(2的倍数压缩省略了) void Find_All_Prime4(vector<int>& vInt_Prime,const int N){ vector<int> vTemp_Prime(N/2,1); //序号 i 对应的数 n 为2*i+1 i=0,1,2,3,.... //n对应的序号为 (n-1)/2 vTemp_Prime[0] = 0; //把1 刷掉 bool Mark = false; for(int Start = 1;Start < N ;++ Start){ // 刷掉的数目是: n^2+2kn (n为素数,k= 0,1,2,3,4.... Mark = false; //2 的倍数自然刷掉,因此从3开始,3对应为i= 1; for(int x = Start;x <vTemp_Prime.size();++ x)//找下一个素数起点 if(vTemp_Prime[x]){ //转换公式为 n^2 +2kn Start = x; //对应 2i^2+2i+ (2i+1)*k Mark = true; break; } if(!Mark) break; if(Start*Start < Start || Start*Start+Start <Start || (2*(Start*Start+Start)<<1) <Start) //排除所有溢出的可能 break; //是否还有合适的素数起点 //由于输入N必然不溢出,溢出说明下一个起点已经超出可能的范围,循环结束. for(int x = 2*(Start * Start+Start); x <= vTemp_Prime.size(); x += Start+Start+1){ vTemp_Prime[x] = 0; } } vInt_Prime.resize(1,2); for(vector<int>::iterator pFirst = vTemp_Prime.begin();pFirst != vTemp_Prime.end();++ pFirst){ if(*pFirst) vInt_Prime.push_back(2*(pFirst-vTemp_Prime.begin())+1); } } class cMy_Bitset{ vector<bitset<32> > vBitset; unsigned in