算法优化 大数据面前的额优化 思路题解1084：用筛法求之N内的素数。 （C++代码）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
    int a,b,i,j,m,n;
    cin>>n;
    cout<<2<<endl;         //2是素数直接输出
 for(i=3;i<=n;i++)      
 {
          a=1;                     
     for(j=2;j<i;j++)       //出去1从2开始并小于自身
     {

         if(i%j==0)           //不满足除自身和一外有因数，a=0表示不是
         {
             a=0;
            break;              //跳出内循环，表示此时i不是素数，开始下一个数的判断
         }
     }
     if(a!=0)              //a=0，不是，a=1是
      cout<<i<<endl;

 }

}

      /***************************************************************/

                                       算法优化

//当n很大时，一下思路仅供参考

/* 根据素数定义，对于给定的正素数n，n是素数的条件是不能被 2,3……n-1整除。这种求素数的方法，当n很大，计算量也很大，效率很低。实际上，任何大于n/2的值不可能被n整除，因此n是素数的条件可以被简化为

不能被2,3...n/2整除。进一步可得n是素数的条件是不能被2,3...根号n整除。

int limit=sqrt(n)+1;              //平方根是浮点数，比如25开根号可能是4.9999  所以
                             //i可能无法判断5这种可能，所以这里加一

     举个例子：16的因数有：1,2,4,8,16，1与16配对，2与8配对，4是16的算术不方根，所以只能与自身配对，从这就可以看出来，一个数只要不能被不超过它的算术平方根整除，那么后面的数也一定不可能有它的因数了。

*/