返回4作为质数的函数

Question

我写了一个函数来检查一个数字是质数还是复合数。它出了点问题。它返回4作为质数。

需要帮助来修复它

int c_sqrt(int nb)
{
    int i;

    i = 1;
    if (nb == 0)
        return (0);
    while (i * i < nb)
        i++;
    if ((nb % i) == 0)
        return (i);
    return (0);
}

int isPrime(int x)
{
    int i;
    int root;

    i = 2;
    root = c_sqrt(x);
    while (i++ <= root)
    {
        if (x % i == 0)
            return (0);
    }
    return (1);
}

Answer 1

您的代码不起作用，因为在下面的几行之后，i变成了3而不是2。

i = 2;
root = c_sqrt(x);
while (i++ <= root)

如果您像下面这样更改增加i的位置，isPrime(4)将是O.K的。

i = 2;
root = c_sqrt(x);
while (i <= root)
{
    if (x % i++ == 0)
        return (0);
}

但是对于像8这样的输入，c_sqrt(int nb)函数也有一些问题，所以你也需要修复它。

/*
if ((nb % i) == 0)
    return (i);
return (0);
*/
return i;

像上面一样，代码的底部实际上不是必需的，只需返回i就足够了。

Answer 2

问题出在while (i++ <= root)上。i从2开始，++递增它，因此您最终直接跳到x % 3并完全跳过x % 2。您可以通过执行while (i <= root)并将++i;添加到循环体的末尾来修复它。或者，您也可以使用for循环，这样会更干净一些。