C 中的质因数

Question

我遇到了这个打印给定数字的所有质因数的有效程序：

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

// A function to print all prime factors of a given number n
void primeFactors(int n)
{
    // Print the number of 2s that divide n
    while (n%2 == 0)
    {
        printf("%d ", 2);
        n = n/2;
    }

    // n must be odd at this point.  So we can skip 
    // one element (Note i = i +2)
    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        // While i divides n, print i and divide n
        while (n%i == 0)
        {
            printf("%d ", i);
            n = n/i;
        }
    }

    // This condition is to handle the case when n 
    // is a prime number greater than 2
    if (n > 2&&n%2!=0)
        printf ("%d ", n);
}

/* Driver program to test above function */
int main()
{
    int n = 315;
    primeFactors(n);
    return 0;
}

输出是 3 3 5 7。太完美了。

但是我对这个算法有一个困惑。 sqrt() returns 一个浮点值。如果它在 printf 中以整数格式显示，它 returns 一些随机的大数字。如果是这种情况，for 循环中的条件应该失败，因为 sqrt() as an integer returns a random number。有人可以解释一下吗？

另外，有人可以验证一下吗？这个算法在 geeksforgeeks 网站上被错误地写成 if(n>2) 而不是 if(n>2&&n!=0)，这是我添加的。有人请验证此算法。提前致谢。

Answer 1

据我从你的问题中了解到，你正在将 float 传递给 printf() 函数，其中 %d 说明符用于 integer。这是 undefined behavior.

N1570 7.21.6.1 第9段：

... If any argument is not the correct type for the corresponding conversion specification, the behavior is undefined.

这就是您看到垃圾值的原因。编译器可能会警告您，但不会在编译时或运行时出错，因为 C 不是 strictly typed language.

编译成功，但输出为-376018152。再说一次，它是 UB。

Answer 2

如果您尝试打印 sqrt(n) 的值，就好像 它是一个整数：

printf("sqrt(n) = %d\n", sqrt(n)); // Don't do this

那么你有未定义的行为。 sqrt() returns 类型 double 的结果。编译器不知道（或不需要知道）参数的预期类型。传递正确类型的参数取决于您。上面对 printf 的调用有未定义的行为。

在其他情况下，表达式的类型和预期类型是明确的，语言需要隐式转换。特别是，在表达式 i <= sqrt(n) 中，其中 i 和 n 的类型为 int，参数 n 从 int 转换为 double（sqrt()的参数类型）, and the value ofiis also converted frominttodouble`。结果很可能就是你所期望的那样。

顺便说一下，这个：

for (int i = 3; i <= sqrt(n); i = i+2) ...

可能效率低下。 sqrt 函数的开销相对较大，它会在循环的每次迭代中被调用。（预计算 sqrt(n) 在某些情况下是一个很好的解决方案，但这里 n 的值可以在循环内改变。）

备选方案是：

for (int i = 3; i*i <= n; i += 2) ...

避免了浮点运算的复杂性（但是想想i*i会不会溢出）

（如果 C 在标准库中有整数平方根函数就好了，但它没有。）

Answer 3

其他人建议预先计算整数平方根，但您需要注意根据需要重新计算。对于主循环，我会使用类似的东西：

// n must be odd at this point.  So we can skip 
// one element (Note i = i +2)
int limit = isqrt(n);  // Calculate integer square root.
for (int i = 3; i <= limit; i = i+2)
{
    // While i divides n, print i and divide n
    if (n % i == 0)
    {
        printf("%d ", i);
        n = n / i;

        while (n%i == 0)
        {
            printf("%d ", i);
            n = n / i;
        }

        // Recalculate limit as n has changed.
        limit = isqrt(n);
    }
}

这只会在测试的数字发生变化时重新计算平方根。我使用 isqrt(n) 来指示进行实际计算的函数。在我自己的代码中，我使用 Newton-Raphson，但还有其他可能的方法。

最后的测试可以简化为：

// This condition is to handle the case when n 
// is a prime number greater than 2
if (n > 1)
{
    printf ("%d ", n);
}

最多有一个质因数大于一个数的平方根。那个单独的因子（如果存在的话）将是除掉所有较小的质因子后的余数。

C 中的质因数

Prime factors in C

c

primes

algebra

sqrt