1

对我说的问题是这样的：

“数字 600851475143 的最大质因数是多少？”

该程序用于使用 C 来找到答案：

#include<math.h> // for remainder because % does not work with double or floats
#include<stdio.h>  
main()
{
    double x=600851475143,y=3.0;
    while(x!=y)                         // divide until only the number can divide itself
    {
        if(remainder((x/y),1)==0.0)     // if x is divisible by y which means it is a factor then do the magic
        {
            x=x/y;                      // divide the number x by y thereby reducing one constituent factor
        }
        y=y+2;                          // add 2 simply because only odd numbers can be prime and hence only prime numbers can be prime factors
    }
    printf("%lf",y);                    // do the printing magic
}

问题正是要问你，我试图检查 x 除以所有奇数，但请注意，并非所有奇数都不是素数，算法中的这个缺陷应该导致答案错误，因为实际上我应该是检查主要因素（不是奇数因素）。

令人惊讶的是，这个程序吐出的答案是正确的，我检查了答案。

我该如何解决这个问题？它没有任何意义。

4

4 回答 4

4

请注意，该算法存在 3 个缺陷：

  1. 2也是质数
  2. 它可能会除非素数和奇数（如 9）
  3. 它不会将素数除一次以上（正如您所期望的那样，它会为诸如 27 之类的数字做）。

从这些我们可以得出结论，如果以下两个条件适用，那么被破坏的算法将产生正确的答案：

  1. 输入数字是奇数（所以跳过 2 无关紧要）
  2. 让数字是所有素数的n = p1*p2*...*p_k地方。p_i对于每个j!=i：p_i != p_j。在这里，这意味着实际上每个素数仅是输入数的一个因数，因此“避免”了问题 2+3。（问题 2 - 为什么要避免它是微不足道的，避免问题 3 是因为您已经将数字与所有相关的素因数相除，所以对于每个m=p_i1*...*p_ic，因为该数字已经除以所有素因数 - p_i1,...p_ic- 您将无法将其除以m.
于 2013-05-14T08:13:25.260 回答
3

由于其他人都在告诉您您的程序出了什么问题，我将给出一个正确的算法来使用试除法分解整数：

function factors(n)
    f, fs := 2, []
    while f * f <= n
        if n % f == 0
            append f to fs
            n := n / f
        else f := f + 1
    append n to fs
    return fs

这解决了您的代码的两个问题。首先，它正确识别 2 的因子。其次，它返回所有因子及其多重性。

回答您关于除以非素数的问题：这是性能问题，而不是正确性问题。由于试验除数是按递增顺序测试的，因此在测试其组成素数时，任何复合除数都已从被分解的数字中删除。这意味着除以复合是没有用的，但不会影响结果。

当然，在处理整数时，你永远不应该使用浮点运算。在 C 语言中，一旦超出 long long 整数，您可能想要切换到gmp库。

有比试除法更好的算法来分解整数，也有比上面显示的更好的方法来实现试除法。但这是一个很好的起点。当你准备好更多时，我谦虚地推荐在我的博客上使用质数编程的文章。

于 2013-05-14T13:09:37.477 回答
2

它之所以有效，是因为您的号码没有重复因素。

600851475143 = 71 * 839 * 1471 * 6857

例如，尝试1573499(23 * 37 * 43 * 43)。

于 2013-05-14T08:33:18.123 回答
1

如果测试的数字是偶数，那么程序将永远运行。x 永远是偶数，y 永远是奇数，所以 x == y 永远不会为真。

如果测试的数字是奇素数或不同奇素数的乘积，则循环将找到除最后一个素数以外的所有素数并除以这些素数，直到只剩下最大的素数，当 y 等于时循环将退出最大的质因数，最大的质因数被打印出来。

有趣的情况是当测试的数字具有奇素数的平方、立方等因素时。循环会找到奇数素因数并除以它们，但例如，如果 3^2 是一个因数，它将除以 3，留下一个因数 3。具体发生的情况取决于素因数。如果只有一个质数平方因数 p^2，程序将不会结束。如果有一个立方体或两个正方形（p^3 或 p^2 q^2），则结果将是错误的剩余因子 p^2 或 pq，除非该数字具有比这更大的素因子。

示例：3^2 x 5^2 x 13：找到因子 3、5 和 13，然后打印 15，这是错误的。示例：3^2 x 5^2 x 17：找到因子 3、5 和 15，然后打印 17，恰好是正确的。

于 2014-03-26T22:42:42.587 回答