/*
题目描述：求出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;
}

评论