判断2147483647这个质数，用了近10秒，吐血。。。

start1980

啊哈C第1页介绍的神奇素数，今天学完了整本书，回过头用代码判断了一下这个质数，结果用了近10秒，书上说用1秒，难道我的电脑是386吗？？什么原因？

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. int main()
   
4. {
   
5.         int a,b,f;
   
6.     a=2147483647;
   
7.     f=1;
   
8.     for(b=2;b<=a-1;b++)
   
9.     {
   
10.                 if(a%b==0)
    
11.                         f=0;
    
12.     }
    
13.     if(f==0)
    
14.                 printf("这是一个合数！");
    
15.     else
    
16.                 printf("这是一个质数！");
    
17.         system("pause");
    
18.         return 0;
    
19. }
    

复制代码

rosynirvana

试除到sqrt(a)就可以了

start1980

sqrt这个函数没学过，如果用这个函数的话，这个程序该如何写？

超神级

.....我会告诉你我的用了30秒吗！

rosynirvana

首先说明，2147483647是一般环境下的INT_MAX，下面代码用的都是INT_MAX以免打错

第一个很慢的版本，也是最平庸的做法，试除到 n/2

1. #include <stdio.h>
   
2. #include <limits.h>
   
3. 
   
4. int main()
   
5. {
   
6.   int is_prime = 1;
   
7.   int div = 2;
   
8.   int upper = INT_MAX/2;
   
9.   for(; div <= upper; ++div)
   
10.     if(INT_MAX % div == 0){
    
11.       is_prime = 0;
    
12.       break;
    
13.   }
    
14.   if(is_prime)
    
15.     printf("%d is a prime\n", INT_MAX);
    
16.   else
    
17.     printf("%d is not a prime\n", INT_MAX);
    
18.   return 0;
    
19. }

复制代码

用POSIX time在我的机器上测定，耗时6.39s

第二个版本，首先把所有偶数都筛掉

1. #include <stdio.h>
   
2. #include <limits.h>
   
3. 
   
4. int main()
   
5. {
   
6.   int is_prime = 1;
   
7.   int div;
   
8. 
   
9.   if(INT_MAX % 2 == 0)
   
10.     is_prime = 0;
    
11.   else
    
12.     for(div = 3; div <= INT_MAX/2; div+=2)
    
13.       if(INT_MAX % div == 0){
    
14.         is_prime = 0;
    
15.         break;
    
16.       }
    
17.   if(is_prime)
    
18.     printf("%d is a prime\n", INT_MAX);
    
19.   else
    
20.     printf("%d is not a prime\n", INT_MAX);
    
21. 
    
22.   return 0;
    
23. }

复制代码

不出意料，时间减少了一半，3.20s

第三个版本，也就是6n±1筛法，把2和3的倍数都筛掉，只用检验6n±1

1. #include <stdio.h>
   
2. #include <limits.h>
   
3. 
   
4. int main()
   
5. {
   
6.   int is_prime = 1;
   
7.   int div;
   
8.   if(INT_MAX % 2 == 0 || INT_MAX % 3 == 0)
   
9.     is_prime = 0;
   
10.   else
    
11.     for(div = 6; div <= INT_MAX/2+1; div += 6)
    
12.       if(INT_MAX % (div-1) == 0 || INT_MAX % (div+1) == 0){
    
13.         is_prime = 0;
    
14.         break;
    
15.       }
    
16. 
    
17.   if(is_prime)
    
18.     printf("%d is a prime", INT_MAX);
    
19.   else
    
20.     printf("%d is not a prime", INT_MAX);
    
21.   return 0;
    
22. }

复制代码

时间减少了大约1/3， 2.12s

最后，试除到sqrt(n)， 并且筛掉所有偶数

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #include <limits.h>
   
4. 
   
5. int main()
   
6. {
   
7.   int is_prime = 1;
   
8.   int upper = sqrt(INT_MAX);
   
9.   if(INT_MAX % 2 == 0)
   
10.     is_prime = 0;
    
11.   else{
    
12.     int div;
    
13.     for(div = 3; div <= upper; div+=2)
    
14.         if(INT_MAX % div == 0){
    
15.             is_prime = 0;
    
16.             break;
    
17.         }
    
18.   }
    
19.   if(is_prime)
    
20.     printf("%d is a prime\n", INT_MAX);
    
21.   else
    
22.     printf("%d is not a prime\n", INT_MAX);
    
23.   return 0;
    
24. }

复制代码

时间测定是0.00s，就不继续往下写了……

超神级

超棒的技巧！！！

start1980

rosynirvana真是牛，原来可以有这么多算法，收藏了，非常感谢！

4399APPLE

我告诉你我的废电脑用了2.5分钟又怎么样······

lzp140

大神哦！！！！！

SeanYuan

大神啊！！！！！！！

隔壁小明

好厉害！！！！！！！

福华

原来程序可以这样写