找到所有小于N的素数

素数问题是个博大精深的问题。我这里只是用一种“相对”高效的算法来查找所有小于某个整数的素数。首先来看一下素数的性质：

1.素数不能被除了1和本身之外所有整数整除

2.1不是素数

3.2是素数

4.除了2之外，所有素数均是奇数

算法使用的思想：小于整数N的任意合数一定可以被小于N开方的素数中其中一个整除；也就是说小于N的整数中，只要不能被小于N开方的任一素数整除，那么它就是素数。这样，根据递归思想，要求出小N的所有素数，则先求出小N开方的所有素数集合a，然后再遍历大于N开方小于N的整数分别除以集合a的所有素数，以求出大于N开方小于N的素数集合b，则a+b即为小于N的所有素数；另外，根据上述性质4，在遍历的时候可以跳过所有偶数。

复杂度分析：

时间复杂度：设小于整数n的算法复杂度为S_n，小于n的所有素数个数为a_n。则时间复杂度的递推公式如下

则个递推公式推起来颇为复杂，我就不算出来了，大概的数量级就是n*a_根号n。由于a_根号n远小于n，所以复杂度远小于n²。

C++算法如下：

#include <cstdlib>
#include <iostream>
#include <vector>
#include <math.h>
#include <ctime>

using namespace std;
vector<int> Find(int lim);
int main(int argc, char *argv[])
{

    time_t b_time,e_time;
    b_time = time(NULL);
    vector<int> arr = Find(1440320);
    e_time = time(NULL);
    cout<<e_time-b_time<<endl;
    cout<<arr.size()<<endl; 
    //for(vector<int>::iterator it=arr.begin();it!=arr.end();++it)
    {
        //cout<<*it<<"|";
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

vector<int> Find(int lim)
{
     //利用素数性质：任何不超过一个数的合数，必被小于这个数开方的素数整除 

     //小于lim的素数 集合 
     vector<int> arr;
     //小于lim开方的素数集合 
     vector<int> a;
     int sqLim = (int)sqrt(lim);
     //if(lim > 10)
     if(lim > 12)
     {
          a = Find(sqLim);
     }
     else
     {
         int rule[5]={2,3,5,7,11};
         a.assign(rule,rule+5);
         return a;
     }

     arr.assign(a.begin(),a.end());

     if(sqLim%2==0)
        sqLim++;
     for(int i=sqLim;i<=lim;i+=2)
     {
          bool flag = true;
          for(vector<int>::iterator it=a.begin();it!=a.end();++it)
          {
                  int s=*it;
                  if(i%s==0)
                  {
                        flag=false;
                  }
          }
          if(flag==true)
             arr.push_back(i);
     }
     return arr;
}

原文链接: https://www.cnblogs.com/joleang/p/3152172.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍