[已解决]请鱼友帮看一下，小甲鱼这个i < num/2 什么意思啊？半天想不通

黑眼睛

程序的功能是判断输入的数是不是素数
#include <stdio.h>

int main()
{
        int i, num;
        _Bool flag = 0;//这一行似懂非懂
        
        printf("请输入一个整数：");
        scanf("%d", &num);
        
        for (i = 2; i < num / 2; i++)//这里为什么要i < num / 2啊，完全不懂。。。
        {
                if (num % i == 0)
                {
                        flag = 0;
                     
                }
               
        }
        if (flag)
        {
                printf("%d是一个素数\n", num);
        }
        else
        {
                printf("%d不是素数\n", num);
        }
        
        return 0;
}

最佳答案

月排行榜 / 总排行榜

召唤风云

2020-9-30 17:30:22

其实这是数学知识，n不除以2也行，只是运算量更大，其实最少运算量的方法是n开根号。
我证明一下合理性吧。用反证法。
如果一个数是合数，则一定能分解成两个不是1的数相乘，所以能被分解成一个大于等于2的数和一个小于等于n/2相乘。
如果这个数没有一个小于等于n/2的因数，那它一定不是合数，所以它一定是素数，不用再检查后面的数了。这里是小于n/2，是因为如果这个数能被n/2整除，那2一定是它的因数，很容易知道2小于等于n/2，所以在检查n/2之前一定检查过2。证明完成！
n开根号也差不多这样证明。

跳转到最佳答案楼层

召唤风云

其实这是数学知识，n不除以2也行，只是运算量更大，其实最少运算量的方法是n开根号。
我证明一下合理性吧。用反证法。
如果一个数是合数，则一定能分解成两个不是1的数相乘，所以能被分解成一个大于等于2的数和一个小于等于n/2相乘。
如果这个数没有一个小于等于n/2的因数，那它一定不是合数，所以它一定是素数，不用再检查后面的数了。这里是小于n/2，是因为如果这个数能被n/2整除，那2一定是它的因数，很容易知道2小于等于n/2，所以在检查n/2之前一定检查过2。证明完成！
n开根号也差不多这样证明。

LuLD

简单来说 一个数的最大因数(不包括自身),不会大于这个数的一半，小甲鱼这样写是减少了运算次数，加快了程序运算，减少了程序运算时间

风过无痕1989

如果数c不是素数，即除其本身和 1 以外，还有其他因子，假如因子为a，b。如果 a = b, c = sqrt(c) * sqrt(c) = sqrt(a) * sqrt(b) ，如果 a <> b，那么，a 与 b 中必有一个大于sqrt(c) ，一个小于sqrt(c) 。故 c 必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。