waixiong 发表于 2021-10-10 22:31:26

关于求素数的代码

#include <stdio.h>
int main()
{
        int i,num;
        bool flag = 1;
        printf("请输入一个整数：");
        scanf("%d",&num);
        for (i= 2; i< num/2; i++ )
        {
                if (num % i == 0)
                {
                        flag= 0;
                }
        }
        if(flag)
        {
                printf("%d是一个素数",num);
        }
        else
        {
                printf("%d不是一个素数",num);
        }
        return 0;
}

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

傻眼貓咪 发表于 2021-10-10 22:31:27

#include <stdio.h>
#include <stdbool.h>

int main(){
    int num;
    bool prime = 1;
   
    printf("输入一个整数：");
    scanf("%d", &num);
   
    /*
    这里从 2 开始测试，假设被 num 除整，则不是素数
    只需测试至 num 的一半便可，
    比如：20（一半是 10）
    20 的所有因数是： 1, 2, 4, 5, 10, 20
    （这里你会发现，因数不会超过 num 的一半，最大的 10 也不用测试，因为 2*10 = 20，2 已经测试过了）
    */
    for(int i=2; i<num/2; i++) if(!(num%i)) prime = 0;
   
    if(prime) printf("%d 是一个素数", num);
    else printf("%d 不是素数", num);
   
    return 0;
}

loverinmydream 发表于 2021-10-10 23:05:51

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

jhq999 发表于 2021-10-11 06:16:05

本帖最后由 jhq999 于 2021-10-11 06:19 编辑

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


          num/=2;
          for (i= 2; i< num; i++ )
      {
                if (num % i == 0)
                {
                        flag= 0;
                        break;
                }
                num/=i;
      }

Shiwellyoung 发表于 2021-10-12 17:52:38

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

真的只会一点点 发表于 2021-10-12 18:49:54

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

18476040601 发表于 2021-10-12 20:07:12

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

帅昊昊昊 发表于 2021-10-12 20:47:30

顶
页: [1]
查看完整版本: 关于求素数的代码