请鱼友帮看一下，小甲鱼这个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;
} 其实这是数学知识，n不除以2也行，只是运算量更大，其实最少运算量的方法是n开根号。
我证明一下合理性吧。用反证法。
如果一个数是合数，则一定能分解成两个不是1的数相乘，所以能被分解成一个大于等于2的数和一个小于等于n/2相乘。
如果这个数没有一个小于等于n/2的因数，那它一定不是合数，所以它一定是素数，不用再检查后面的数了。这里是小于n/2，是因为如果这个数能被n/2整除，那2一定是它的因数，很容易知道2小于等于n/2，所以在检查n/2之前一定检查过2。证明完成！
n开根号也差不多这样证明。
简单来说 一个数的最大因数(不包括自身),不会大于这个数的一半，小甲鱼这样写是减少了运算次数，加快了程序运算，减少了程序运算时间 如果数c不是素数，即除其本身和 1 以外，还有其他因子，假如因子为a，b。如果 a = b, c = sqrt(c) * sqrt(c) = sqrt(a) * sqrt(b) ，如果 a <> b，那么，a 与 b 中必有一个大于sqrt(c) ，一个小于sqrt(c) 。故 c 必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。
页:
[1]