C语言快速判断素数——不超时

C语言快速判断素数——不超时

这属于算法上的问题，好好考虑一下算法，还要考虑一下素数的定义。

 
素数是只有1和本身能整除的整数。

所以在求素数的时候，要将素数与1到素数本身中间的所有整数都相除，看是否有整除的数，如果有，那肯定不是素数了。

但是从算法上考虑，为了减少重复量，开平方后面的数就不用相除了，因为a/b（平方数）=c（小一点的数），同样a/c=b。

举例说明： 
25，开平方以后是5,那么整除2~5就可以了，如果有满足条件的，就是素数。

 
这样做可以减少循环次数，素数是因子为1和本身， 如果数c不是素数，则还有其他因子，其中的因子，假如为a,b.其中必有一个大于sqrt(c) ，一个小于sqrt(c) 。

所以m必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。

即一个合数一定含有小于它平方根的质因子。

再比如：24的因数有1、2、3、4、6、8、12、24 
按定义应该用2－23去除，但经过分析上面的数可以发现 
1×24、2×12、3×8、4×6 
如果2、3、4是某个数的因数，那么另外几个数也是，反之也一样 
所以为提高效率，可以只检查小于该数平方根的那些数，如24的平方根大于4小于5，检查2－4就可以了！

例如：问题：令Pi表示第i个素数。

现任给两个正整数M <= N <= 10000，请输出PM到PN的所有素数。

我的代码：

红色部分为应用sqrt方法快速判断是否为素数，防止超时:

 #include <stdio.h>

 #include <stdlib.h>

 #include<stdbool.h>

 #include<math.h>

 int main()

 {

     int min,max;

     scanf("%d",&min);

     scanf("%d",&max);

     int i=,sushu[],num=;

     sushu[]=;

     while(i<max){

14         bool tag=true;

15         for(int k=2;k<=sqrt(num);k++){

16             if(num%k==0){

17                 tag=false;//判断不是素数

18                 break;

19             }

20         }

21         if(tag){

22             sushu[i]=num;

23             i++;

24         }

25         num+=2;

26     }

     int m=;

     for(int k=min-;k<max;k++){

         m++;

         if(k==max-){

             printf("%d",sushu[k]);

         }else{

             if(m%==){

                 printf("%d\n",sushu[k]);

             }else{

                 printf("%d ",sushu[k]);

             }

         }

     }

     return ;

 }