[已解决]关于求素数的代码

waixiong

1. #include <stdio.h>
   
2. int main()
   
3. {
   
4.         int i,num;
   
5.         bool flag = 1;
   
6.         printf("请输入一个整数：");
   
7.         scanf("%d",&num);
   
8.         for (i= 2; i< num/2; i++ )
   
9.         {
   
10.                 if (num % i == 0)
    
11.                 {
    
12.                         flag= 0;
    
13.                 }
    
14.         }
    
15.         if(flag)
    
16.         {
    
17.                 printf("%d是一个素数",num);
    
18.         }
    
19.         else
    
20.         {
    
21.                 printf("%d不是一个素数",num);
    
22.         }
    
23.         return 0;
    
24. }

复制代码

请问能解释一下for循环的用处吗？看不懂

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2021-10-10 22:31:27

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. 
   
4. int main(){
   
5.     int num;
   
6.     bool prime = 1;
   
7.    
   
8.     printf("输入一个整数：");
   
9.     scanf("%d", &num);
   
10.    
    
11.     /*
    
12.     这里从 2 开始测试，假设被 num 除整，则不是素数
    
13.     只需测试至 num 的一半便可，
    
14.     比如：20（一半是 10）
    
15.     20 的所有因数是： 1, 2, 4, 5, 10, 20
    
16.     （这里你会发现，因数不会超过 num 的一半，最大的 10 也不用测试，因为 2*10 = 20，2 已经测试过了）
    
17.     */
    
18.     for(int i=2; i<num/2; i++) if(!(num%i)) prime = 0;
    
19.    
    
20.     if(prime) printf("%d 是一个素数", num);
    
21.     else printf("%d 不是素数", num);
    
22.    
    
23.     return 0;
    
24. }

复制代码

跳转到最佳答案楼层

傻眼貓咪

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. 
   
4. int main(){
   
5.     int num;
   
6.     bool prime = 1;
   
7.    
   
8.     printf("输入一个整数：");
   
9.     scanf("%d", &num);
   
10.    
    
11.     /*
    
12.     这里从 2 开始测试，假设被 num 除整，则不是素数
    
13.     只需测试至 num 的一半便可，
    
14.     比如：20（一半是 10）
    
15.     20 的所有因数是： 1, 2, 4, 5, 10, 20
    
16.     （这里你会发现，因数不会超过 num 的一半，最大的 10 也不用测试，因为 2*10 = 20，2 已经测试过了）
    
17.     */
    
18.     for(int i=2; i<num/2; i++) if(!(num%i)) prime = 0;
    
19.    
    
20.     if(prime) printf("%d 是一个素数", num);
    
21.     else printf("%d 不是素数", num);
    
22.    
    
23.     return 0;
    
24. }

复制代码

loverinmydream

循环将变量i初始化为2，每次循环结束都加1， 循环继续的条件是i<num/2

jhq999

因为合数能被整除的最小值一定大于等于2，所以最大值为它的1/2；
感觉应该还能更有效率；

1. 
   
2.           num/=2;
   
3.           for (i= 2; i< num; i++ )
   
4.         {
   
5.                 if (num % i == 0)
   
6.                 {
   
7.                         flag= 0;
   
8.                         break;
   
9.                 }
   
10.                 num/=i;
    
11.         }
    

复制代码

Shiwellyoung

一个数字可以除尽的数一定不能大于它 的一半（6最大可以除以3，8最大可以初以4）所以循环的条件就到num/2就可以了

真的只会一点点

判断一个素数方法有一个正数n，设p是小于n的1/2次方的素数，如果p能整除n,则n不是素数，反之是。这里的for循环里用num/2来代替n的1/2，i就相当于p（这种说法严格来说是不对的，只是我尝试让你理解）

18476040601

因为素数是不能被任何数整除 ， 因子只能为1 和它本身 ，所以如果它从2到它本身的一半逐个不能被整除，即为素数。

帅昊昊昊

顶