快速查找素数

 //根据概念判断:

 //如果一个正整数只有两个因子, 1和p，则称p为素数.

 //代码:

 bool isPrime(int n)

 {

     if(n < ) return false;

     for(int i = ; i < n; ++i)

         if(n%i == ) return false;

     return true;

 }

 //时间复杂度O(n)

 //改进, 去掉偶数的判断

 //代码:

 bool isPrime(int n)

 {

     if(n < ) return false;

     if(n == ) return true;

     if(n %  == ) return false;

     for(int i = ; i < n; i += )

         if(n%i == ) return false;

     return true;

 }

 //时间复杂度O(n/2), 速度提高一倍.

 /进一步减少判断的范围

 //定理: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d.

 //证明: 如果n不是素数, 则由定义n有一个因子d满足1<d<n.

 //如果d大于sqrt(n), 则n/d是满足1<n/d<=sqrt(n)的一个因子.

 //代码:

 bool isPrime(int n)

 {

     if(n < ) return false;

     if(n == ) return true;

     if(n %  == ) return false;

     for(int i = ; i*i <= n; i += )

         if(n%i == ) return false;

     return true;

 }

 //时间复杂度O(sqrt(n)/2), 速度提高O((n-sqrt(n))/2).

 //筛法判断素数 一

 #include<cstdio>

 #define MAXN 2000001

 int a[MAXN],i,j;

 int main(){

     int m;

     //筛选出二百万内的所有素数

     for(i = ;i <= ;i++){

         if(a[i]==)

             //利用数组的下标，将i的倍数全部筛掉

             for(j = i + i;j <= ;j += i)

                 a[j] = ;

     }

     while(scanf("%d",&m) && m!=){

         //从数组中依据下标取出[2,m]内的所有素数

         for(i = ;i <= m;i++){

             if(a[i] == ){

                 printf("%d ",i);

             }

         }

         printf("\n");

     }

     return ;

 }

 //筛法判断素数 二

 #include<cstdio>

 #define MAXN 2000001

 int a[MAXN],i,j;

 int main(){

     int m;

     while(scanf("%d",&m) ==  && m!=){

         //m有多大，数组用多大

         for(i = ;i <= m;i++)

             a[i] =i;

         //m/2缩小范围

         for(i = ;i <= m/;i++){

             if(a[i] != ){

                 for(j=i+i;j <= m;j += i){

                     //将i的倍数全部筛掉

                     a[j] = ;

                 }

             }

         }

         for(i = ;i <= m;i++){

             if(a[i] != ) printf("%d\n",a[i]);

         }

     //    printf("\n");

     }

     return ;

 }