鱼C论坛

 找回密码
 立即注册
查看: 174|回复: 7

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

[复制链接]
发表于 2021-10-10 22:31:26 | 显示全部楼层 |阅读模式
2鱼币
  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. int main(){
  4.     int num;
  5.     bool prime = 1;
  6.    
  7.     printf("输入一个整数:");
  8.     scanf("%d", &num);
  9.    
  10.     /*
  11.     这里从 2 开始测试,假设被 num 除整,则不是素数
  12.     只需测试至 num 的一半便可,
  13.     比如:20(一半是 10)
  14.     20 的所有因数是: 1, 2, 4, 5, 10, 20
  15.     (这里你会发现,因数不会超过 num 的一半,最大的 10 也不用测试,因为 2*10 = 20,2 已经测试过了)
  16.     */
  17.     for(int i=2; i<num/2; i++) if(!(num%i)) prime = 0;
  18.    
  19.     if(prime) printf("%d 是一个素数", num);
  20.     else printf("%d 不是素数", num);
  21.    
  22.     return 0;
  23. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-10-10 22:31:27 | 显示全部楼层    本楼为最佳答案   
  1. #include <stdio.h>
  2. #include <stdbool.h>

  3. int main(){
  4.     int num;
  5.     bool prime = 1;
  6.    
  7.     printf("输入一个整数:");
  8.     scanf("%d", &num);
  9.    
  10.     /*
  11.     这里从 2 开始测试,假设被 num 除整,则不是素数
  12.     只需测试至 num 的一半便可,
  13.     比如:20(一半是 10)
  14.     20 的所有因数是: 1, 2, 4, 5, 10, 20
  15.     (这里你会发现,因数不会超过 num 的一半,最大的 10 也不用测试,因为 2*10 = 20,2 已经测试过了)
  16.     */
  17.     for(int i=2; i<num/2; i++) if(!(num%i)) prime = 0;
  18.    
  19.     if(prime) printf("%d 是一个素数", num);
  20.     else printf("%d 不是素数", num);
  21.    
  22.     return 0;
  23. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-10-10 23:05:51 | 显示全部楼层
循环将变量i初始化为2,每次循环结束都加1, 循环继续的条件是i<num/2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-10-11 06:16:05 | 显示全部楼层
本帖最后由 jhq999 于 2021-10-11 06:19 编辑

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


  1.           num/=2;
  2.           for (i= 2; i< num; i++ )
  3.         {
  4.                 if (num % i == 0)
  5.                 {
  6.                         flag= 0;
  7.                         break;
  8.                 }
  9.                 num/=i;
  10.         }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-10-12 17:52:38 | 显示全部楼层
一个数字可以除尽的数一定不能大于它 的一半(6最大可以除以3,8最大可以初以4)所以循环的条件就到num/2就可以了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-10-12 18:49:54 | 显示全部楼层
判断一个素数方法有一个正数n,设p是小于n的1/2次方的素数,如果p能整除n,则n不是素数,反之是。这里的for循环里用num/2来代替n的1/2,i就相当于p(这种说法严格来说是不对的,只是我尝试让你理解)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-10-12 20:07:12 | 显示全部楼层
因为素数是不能被任何数整除 , 因子只能为1 和它本身 ,所以如果它从2到它本身的一半逐个不能被整除,即为素数。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-10-12 20:47:30 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2021-10-23 02:27

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表