-5

以下代码用于质数。我想知道为什么我们i<=n/2在循环中使用条件。

C程序：

#include <stdio.h>
int main()
{
int n, i, flag = 0;

printf("Enter a positive integer: ");
scanf("%d",&n);

for(i=2; i<=n/2; ++i)
{
    // condition for nonprime number
    if(n%i==0)
    {
        flag=1;
        break;
    }
}

if (flag==0)
    printf("%d is a prime number.",n);
else
    printf("%d is not a prime number.",n);

return 0;
}
4

2 回答 2

9

虽然这是 C 程序。但素数逻辑对于 C 和 Java 都是相同的

素数
每个只能被 1 整除的自然数和它本身都是素数。此外，2 是第一个素数。

例如，我们要测试数字 100 是否为质数。我们可以做一个试除法来测试 100 的素数。

让我们看看 100 的所有除数：

2、4、5、10、20、25、50

这里我们看到最大因子是 100/2 = 50。这对所有 n 都是正确的：所有除数都小于或等于 n/2。

所以这里的条件 i<=n/2 条件是正确的。因为我们只需要测试最多 n/2 的除数。

请查看 Wiki 链接以获取更多详细信息 https://en.wikipedia.org/wiki/Primality_test

第二个例子

同样，对于 11，您将检查所有小于 5.5 的整数，即 1、2、3、4 和 5。

找到一个数是素数，为什么检查到 n/2 更好。n后半段避免numbres的原因是什么

于 2017-10-26T16:47:02.257 回答
0

任何数字 n 的最大因子必须 <= n/2，因此无需检查更大的数字

于 2018-09-15T23:14:42.400 回答