时间戳

首页 > 解决方案 > C中的素数

c - C中的素数

问题描述

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

# 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 网站上被错误地写为 if(n>2) 而不是我添加的 if(n>2&&n!=0)。有人请验证此算法。提前致谢。

标签： cprimesalgebrasqrt

解决方案

如果您尝试将 的值打印sqrt(n) 为整数：

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

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

在其他上下文中，表达式的类型和预期类型是明确的，该语言需要隐式转换。特别是，在表达式i <= sqrt(n)wherei和nare 的类型int中，参数n被转换int为double（参数类型sqrt()）, and the value ofi is also converted fromint 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 在标准库中有一个整数平方根函数会很好，但它没有。）

推荐阅读