质数逻辑，循环中的 n/2 条件 [英] Prime number Logic, n/2 condition in a loop

问题描述

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

The following code is for prime number. I want to know why we use i<=n/2 condition in the loop.

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;
}

推荐答案

虽然这是 C 程序.但是质数逻辑对于 C 和 Java 都是一样的

Although this is C program. But prime number logic will be same for C and Java both

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

Prime number
Each natural number that is divisible only by 1 and itself is prime. Also, 2 is the first prime number.

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

For example, we want to test that number 100 is a prime number or not. we can do a trial division to test the primality of 100.

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

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

2, 4, 5, 10, 20, 25, 50

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

Here we see that the largest factor is 100/2 = 50. This is true for all n: all divisors are less than or equal to n/2.

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

So here condition i<=n/2 condition is correct. Since we need to test divisors up to n/2 only.

请查看维基链接了解更多详情https://en.wikipedia.org/wiki/Primality_test

Please check the Wiki link for more detail https://en.wikipedia.org/wiki/Primality_test

第二个例子

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

Similarly, for 11 you would check all integers smaller than 5.5, i.e. 1, 2, 3, 4 and 5.

找到一个数是素数，为什么检查到 n/2 更好.n 后半部分避免数字的原因是什么

这篇关于质数逻辑，循环中的 n/2 条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！