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()返回浮点值.如果以整数格式显示printf,则返回一些随机的大数字.如果是这种情况,for循环中的条件应该失败,因为sqrt()整数返回一个随机数.有人可以解释一下吗？

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

Answer 1

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

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

那么你有未定义的行为.sqrt()返回类型的结果double.编译器不知道(或不需要知道)参数的预期类型.由你来传递正确类型的参数.上面的调用printf具有未定义的行为.

在其他上下文中,表达式的类型和期望类型是明确的,语言需要隐式转换.特别地,在表达i <= sqrt(n),在那里i和n是类型的int,参数n被从转换int到double(参数类型为sqrt()), and the value of我is also converted from诠释todouble`.结果很可能是您的预期.

顺便说一下,这个:

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在标准库中有一个整数平方根函数会很好,但事实并非如此.)