C 编程 - 检查质数

Question

我正在尝试检查给定数字是否为素数，但我运行遇到了问题。这是代码：

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

bool isPrime(int input)
{
    for (int i = sqrt(input); i >= 2; i--)
    {
        if (input % i == 0)
        {
            return false;
        }
    return true; 
    }
    
}

int main()
{
    int input;
    scanf("%d", &input);
    
    if (isPrime(input))
    {
        printf("Is prime number");
    } else
    {
        printf("Is not prime number");
    }
    
    return 0;
}

在我的isPrime函数的代码块中，如果我像上面那样把return true;放在for循环中，在某些情况下这是错误的（例如，当input是 10，它会声明 10 是质数）。但是，如果我将 return true; 放在 for 循环之外，它就可以正常工作。那么有什么区别呢？

Answer 1

当您将 return true; 放入循环中时，只要前面的 if 条件为假，就会执行该语句。一旦完成 for 循环并且没有找到除数，您只想 return true。这就是为什么 return 语句需要在循环之外。

Answer 2

如果 for 循环中的第一个除数不除以目标数，则函数 return 为真。

因为这个return声明

    return true;

在 for 循环内。

bool isPrime(int input)
{
    for (int i = sqrt(input); i >= 2; i--)
    {
        if (input % i == 0)
        {
            return false;
        }
    return true; 
    }
    
}

此外，如果函数被调用为素数 2 或 3 或者如果将 non-positive 数字传递给函数，则该函数具有未定义的行为。

放置return语句

return true;

循环外不会使您的函数正确。

注意检查偶数除了2是质数还是非质数是没有意义的

函数可以这样写

bool isPrime( unsigned long long n )
{
    bool prime = n % 2 == 0 ? n == 2 : n != 1;

    for ( unsigned long long int i = 3; prime && i <= n / i; i += 2 )
    {
        prime = n % i != 0;
    }

    return prime;  
}

函数可以这样调用

unsigned int input;
scanf("%u", &input);

if (isPrime(input))
{
    printf("Is prime number");
} else
{
    printf("Is not prime number");
}

Answer 3

发生这种情况是因为您的 for 循环没有完成 i 的完整遍历，但是 return true 语句告诉代码在您的 if 条件第一次变为假时执行它，然后退出环形。所以，想象一下，我给你 10 块巧克力，告诉你每块都咬一口，并且只收集深色的。你先咬了一口，它很甜，你把它收起来了。你咬第二口，天就黑了。你收集它并告诉我你完成了，虽然你实际上没有（你没有检查其余的巧克力棒看是否有更多的深色巧克力棒）。这就是您在代码中所做的。希望示例清晰且有用:)

Answer 4

让我们来看看你的循环：

for (int i = sqrt(input); i >= 2; i--)
{

如果输入为 10，则 i 开始为 3（请记住，将 floating-point 值分配给 int 时，小数部分被丢弃）。 3大于等于2，所以执行循环体

    if (input % i == 0)
    {

10除以3的余数不为零，所以我们不进入if语句的主体。

        return false;
    }
return true; 
}

然后我们马上returntrue.

因此，无论您提供什么输入，您的循环都只会迭代 1 次。如果 input 可以被其平方根的整数值整除（例如 9、16 或 25），则 if 的主体语句被执行并且它returns false，否则它无条件地 returns true.

为了您的函数正常工作，您必须将 return true; 语句移到循环体之外 - 您应该只 return true 当您用尽 sqrt(input) 和 2 之间的所有 i 值时。

C 编程 - 检查质数

C programming - Checking prime number

c

primes

loops

for-loop

function-definition