[已解决]请问这种判断数值是否为质数的方法的原理是什么呢

suchenxiang

#include<stdio.h>
#include<stdbool.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是一个素数！\n",num);
         }
         else
         {
                 printf("%d不是一个素数!\n",num);
         }
         return 0;
}

最佳答案

月排行榜 / 总排行榜

ckg16

2022-2-7 12:19:33

flag 代表 是否是素数
for 循环里从2到num/2进行搜索，确认原数没有除1 or 原数 以外的因子
其实可以进一步优化，加入#include<cmath>,然后将num/2改成sqrt(num)

跳转到最佳答案楼层

Twilight6

这原理就是质数的概念：若一个大于二的自然整数 只能被 1 和 自身 整除，那么该数就是质数

所以这里用 flag 参数记录下是否被某个值整除过，若被除了 1 和自身的数整除 那么自然不是质数，即 flag 设置为 0，说明不是质数

ckg16

flag 代表 是否是素数
for 循环里从2到num/2进行搜索，确认原数没有除1 or 原数 以外的因子
其实可以进一步优化，加入#include<cmath>,然后将num/2改成sqrt(num)