/*题目描述：求出N内的所有素数，把他们存储到数组sushu[MAX] 中，并返回素数的个数。算法描述：在下面的程序中我分别使用了常规方法和新方法求素数表，结果新方法所用时间远小于常规方法。新方法的思路其实不新，只是利用了一个小技巧：一个正整数如果不能被所有不大于它的平方根的素数整除，则它一定是素数。我在判断正整数i是否为素数时，不是让它去整除每一个不大于它的平方根的正整数，而是让它去整除已经得到的素数表中的素数（此时素数表中的素数比i要小），这样就大大地减少了运算量。注意：另外还有一种类似桶式排序的方法，是把所要分析的正整数作为布尔数组p[N]的下标，先给布尔数组p[N]赋初值为true。从i=2开始分析，若p[i]==true，则i的所有倍数j=n*i均为非素数，将以j为下标的元素p[j]==false；直到i==N/2结束分析。遍历布尔数组p[N]，若若p[i]==true，则表示i为素数，将其存入素数表。这种方法速度也很快，但它需要设置一个长度为N的布尔数组p[N]，当N很大时，会占用过多内存空间，导致程序不能执行。*/#include <iostream>#include <math.h>#include <time.h>using namespace std;long Sushu_1(long a[], long n);long Sushu_2(long a[], long n);long Sushu_3(long a[], long n);int main(){ const long MAX = 150000; //预计素数总的个数 const long N = 2000000; //被分析的数的最大值，若执行Sushu_3()，N不能超过1000000 ////////////////////////////////////////////////////////////// time_t startTime_1; time_t endTime_1; time(&startTime_1); long sushu_1[MAX] = {0}; long top_1 = Sushu_1(sushu_1, N);//使用常规方法求素数表 cout << "top_1 = " << top_1 << endl; time(&endTime_1); cout << "time_1 = " << difftime(endTime_1, startTime_1) << endl; //////////////////////////////////////////////////////////////// time_t startTime_2; time_t endTime_2; time(&startTime_2); long sushu_2[MAX] = {0}; long top_2 = Sushu_2(sushu_2, N); //使用新方法求素数表 cout << "top_2 = " << top_2 << endl; time(&endTime_2); cout << "time_2 = " << difftime(endTime_2, startTime_2) << endl; //////////////////////////////////////////////////////////////// //time_t startTime_3;// time_t endTime_3;// time(&startTime_3);//// long sushu_3[MAX] = {0};// long top_3 = Sushu_3(sushu_3, N); //使用桶式排序的方法求素数表// cout << "top_3 = " << top_3 << endl;//// time(&endTime_3);// cout << "time_3 = " << difftime(endTime_3, startTime_3) << endl; //////////////////////////////////////////////////////////////// getchar(); return 0;}long Sushu_1(long a[], long n)//使用常规方法求素数表{ a[0] = 2; long top = 1; for (long i=3; i<=n; i+=2) { long q = (long)sqrt(i); bool flag = true; for (long j=2; j<=q; j++) { if (i%j == 0) { flag = false; break; } } if (flag) a[top++] = i; } return top;}long Sushu_2(long a[], long n)//使用新方法求素数表{ a[0] = 2; long top = 1; for (long i=3; i<=n; i+=2) { long q = (long)sqrt(i); bool flag = true; for (long j=0; a[j]<=q && j<top; j++) { if (i%a[j] == 0) { flag = false; break; } } if (flag) a[top++] = i; } return top;}long Sushu_3(long a[], long n) //使用桶式排序的方法求素数表，n不能太大{ bool *p = new bool[n+1]; for (long i=0; i<=n; i++) p[i] = true; long m = n / 2; for (long i=2; i<=m; i++) { if (p[i])//若i为素数，则i的整数倍必为非素数 { for (long j=2*i; j<=n; j+=i) p[j] = false; } } long top = 0; for (long i=2; i<=n; i++)//累积素数 if (p[i]) a[top++] = i; delete []p; return top;} 补充一个: 来源:http://blog.vckbase.com/smileonce/archive/2004/11/09/1394.html?Pending=true#Post 求素数的爱沙托散筛法 //author: smileonce #include <iostream> using namespace std; static const int N = 1000; int main(int argc, char *argv[]) { int i, a[N]; for (i=2; i<N; i++) a[i] = 1; for (i=2; i<N; i++) if (a[i]) for(int j=i; j*i<N; j++) a[i*j] = 0; for (i=2; i<N; i++) if (a[i]) cout << " " << i; cout << endl; return 0; }
评论