•  18-09-2019
  •  | 
  •  

题

我想写一个程序找到最大的主要因素的一个非常大的数量，并已经尝试了几种方法与不同的成功。所有的那些我们发现迄今为止已经令人难以置信的速度慢。我有一个想法，我想知道如果这是一个有效的方法：

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

这个办法将采取的输入，并且将会做到以下几点：

200 -> 100 -> 50 -> 25 -> 5 (返回)

90 -> 45 -> 15 -> 5 (返回)

它将currentNum多次通过最小可分割的数量(最多2个，或者3)，直到currentNum本身是总理(有不可分割的总数低于平方根的currentNum)，并假定这是最大的主要因素的原输入。

将这始终是工作吗？如果不是，可能有人给我一个反?

-

编辑：通过非常大，我的意思是约2^40、或10^11.

有帮助吗？

解决方案

这将永远因为独特总理因式分解的工作。

其他提示

该方法将工作，但将是缓慢的。"有多大你的号码？"确定该方法的使用：

当然，它会工作（见马克Byers公司的回答），但对于“非常大”的投入可能需要的时间太长了。你应该注意到，您对getLowestDivisiblePrimeNumber()调用隐藏另一个循环，所以这个运行在O（N ^ 2），这取决于你所说的“非常大”是什么，可能要对的大数这将是缓慢的。

您可能会加速它的一点点，通过注意你的算法需要从不检查发现比最后一个小因素。

您正在试图找到首要因素一些。你所提出的工作，但仍将是大量慢....你应该感谢这一点，因为大多数现代证券在这是一个棘手的问题前提。

这是一个快速搜索我只是做了，目前最快的办法因素一批是利用椭圆曲线的方法。

您可以尝试在这个演示投掷您的号码： http://www.alpertron.com .ar / ECM.HTM 。

如果这会让你确信，你可以尝试或者窃取代码（这是没有什么好玩的，他们提供了一个链接到它！）或其他地方在它的理论读了。这里有一个关于它的维基百科文章： http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization但我太傻去了解它。值得庆幸的是，这是你的问题，不是我的！ ：）

与项目欧拉的事情是，通常有明显的穷举法做的问题，这将几乎永远。随着问题变得更加困难，你将需要实现聪明的解决方案。

就可以解决这个问题的一种方法是使用一个循环，总能找到一个数字的最小（正整数）的因素。当数最小的因素是数字，那么你已经找到了最伟大的首要因素！

详细算法描述：

您可以通过保持三个变量做到这一点：

你试图因子数（A） 电流除数存储（B） 甲最大除数存储（C）

首先，让（A）是有兴趣的数量 - 在这种情况下，它是600851475143.然后让（B）是2.有一个条件是，如果检查（A）是由（B）整除。如果是整除，除（A）由（B），复位（B）为2，回去检查，如果（A）是（B）整除。否则，如果（A）是不被（B），增量（B）整除1，然后检查（A）是由（B）整除。运行循环，直到（A）为1（3）您返回将是600851475143的最大素因子。

有很多方法，你可以让这个更有效的 - 而不是递增到下一个整数，你可以递增到下一个必然素数，而不是保持最大除数商店，你可以只当返回当前号码的只有除数是本身。然而，我上述算法将在几秒钟内运行而不管

在python的实施如下： - 

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

例：让我们发现使用上述的方法105的最大素数因子

。

让（A）= 105（B）= 2（我们总是用2开始），并且我们没有一个值（C），但

时（A）整除（B）？号递增（B）由1：（B）= 3是是（A）由（B）整除？是。 （三分之一百○五= 35）。迄今发现的最大的除数是3设（C）= 3，更新（A）= 35复位（B）= 2。

现在，是（A）整除（B）？号递增（B）由1：（B）= 3是（A）由（B）整除？号递增（B）由1：（B）= 4为（a）由（B）整除？号递增（B）由1：（B）= 5为（A）由（B）整除？是。 （35/5 = 7）。我们以前发现的最大除数存储在（C）。 （C）是目前3. 5大于3，所以我们更新（C）= 5，我们更新（A）= 7。我们重置（B）= 2。

然后，我们不断为（A）的过程，但我们会不断递增（B），直到（B）=（A），因为7是素数，有没有比它本身和1以外除数（我们可能已经停止当（B）>（（A）/ 2），作为不能有整数除数比数的一半更大！ - 最小可能的除数（除1以外）的任何数目为2）

因此，在这一点上，我们返回（A）= 7。

尝试用手做了几个，你会明白我的意思的窍门

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top