问题标签 [factorization]

我正在尝试从http://projecteuler.net解决问题 3 。但是，当我运行东西程序时，什么都没有打印出来。我究竟做错了什么？问题：数字 600851475143 的最大质因数是多少？

我正在尝试编写的程序需要输入用户定义的 Int 值数量并产生这些值的乘积，然后确定该乘积的所有因素。这些值将通过一个 Do-While 循环输入，直到用户输入一个负数，然后所有的正数将相乘，形成一个 Double 形式的乘积。我相当肯定我可以弄清楚如何获得产品的因素，但是在找到实际产品时，我完全不知所措。这是我到目前为止编写的代码，减去我在生产产品方面的失败尝试。

这就是我能够弄清楚的全部，循环 Value 提示直到输入负 Int 。就获得产品而言，我在循环内部和外部都尝试过 If-Statements，但要么我的代码错误，要么我的语句错误，或者更有可能我只是尝试了错误的方法。我不是要求任何人为我编写代码，但如果有人能指出我正确的方向，我将非常感激。

您建议从未知数量的用户定义值中确定产品的建议是什么？

此方法采用 int - 但是我不断收到错误消息，有人知道为什么吗？

我正在制作两个类，构造类和主要方法，我从用户输入中读取一个数字并吐出数字的主要分解，代码使用 Java。

例如：
输入号码：150
5
5
3
2

但是，对于我的程序，我得到了完整的因素列表。

示例：
输入号码：150
150
75
50
25
5
3
1

我将如何改变它以获得主要因素？

主要方法：

这是我的课：

The question is in the title. Now to make the term self-product more clear. Self-product means the product of the number and its digits. Example:

Self-Product(1234) = 1234*1*2*3*4 = 29616.

I've tried two methods.

Brute-force

Anyone's idea would be to check all combinations between 1 and N (upper bound of the range). And check if the number's self-product is within the range. This would be ideal for relativly low numbers, but having in mind that the range can be big as 10^20, it's becoming a problem, because it'll take a while before it prints the result.

Factorization

Another idea is to factorize the number within the range. If the range is between 60 000 and 70 000, when I check for 62 688, I'll get 62 688 as 2*2*2*2*2*3*653. Now knowing that 653 can't be a digit, that means that it have to be in the original number. Then again I have to combine all factors of 62 688 to get the right answer and it should output that this one is Self-Product of 2612, beacuse 62 688 = 2612 * 2 * 6 * 1 * 2.

In both situation I face a big problem, which is checking all of the combinations.

P.S I found that if number has n-digit then if it's self-product of some number than that number would have at least n/2 digits and no more than n. This would make the list of numbers that I will need to check a little bit smaller, but it doesn't solve the problem.

我有一个尺寸为 6x6 的矩阵 M，它的秩为 1。我如何将它分解为两个尺寸为 6x1（比如 A）和 1x6（比如 B）的矩阵，以便 M=A*B。

你知道 MATLAB 是否支持 LAPACKspptrf功能。

当你需要计算一个巨大的正定对称矩阵的 Cholesky 分解时，这个函数是相当划算的。

它通过仅给出存储为一维矩阵的上三角矩阵作为输入来允许分解。

或者，chol内置函数是否已经在spptrf内部使用？

编辑

我已经能够在文件交换http://www.mathworks.com/matlabcentral/fileexchange/16777-lapacklapack上找到该库，并具有所需的功能实现。spptrf

编辑 2

每次我调用 MATLAB 在我的机器上运行都会致命地崩溃spptrf。

有没有其他方法可以直接处理这个函数？

从标题可以看出，我正在努力尝试对因数为 2 个素数的大整数进行因式分解。我想知道是否有一种方法可以为此在 for 循环中使用 for 循环。我知道这是一种可怕的方法，但我还是想这样做。（我打算使用 fermats 因式分解定理，但如果没有一些额外的方法/库，你就不能 sqrt BigIntegers，我不能这样做）所以试着看看你是否能帮助我做我正在做的事情。大致上是这样的：

显然那太糟糕了，我知道你不能通过说 i.nextPossiblePrime() 来增加下一个素数，你需要它说 i = i.nextpossible prime，我只是向你展示了我希望它如何工作; 但这就是我问的原因，因为我想知道这样的事情是否可能！

请让我知道这条路线是否可行，以及我如何修复这个糟糕的代码以像我想象的那样运行！

谢谢！

给定方程：

我试过的解决方案：

我们已经知道的术语：A、B、C、D、K

在给定 p, q, r 的情况下找到术语 s；

继续直到s 变为 < 0； 对于所有项 p=0, q=0, r=1...n;

同样继续，直到s 变为 < 0； 对于 p=0, q=1..n, r=1...n 的所有项；

和，

最后，继续直到s 变为 < 0； 对于 p=1..n、q=1..n 和 r=1..n 的所有项；

编码 3 个循环用于更新 p、q 和 r。

如果 K 变大，例如 1000...、8145、45000 等，则需要更多时间来计算；

请不要建议外部库...我正在寻找编码解决方案。

示例片段

另外，如果有人注意到：preSpecifiedIterations -> 是否可以确定在计算之前需要多少次迭代？

有没有更好的算法来解决上述问题？

非常感谢阅读。

我正在尝试在 Python 中实现 Pollard 的 P-1 分解。请注意，Rho 方法有一些答案，但这个 p-1 是不同的，关于 p-1，我可以在这里为您提供的最好的答案是 wiki 和 Wolfram：

http://en.wikipedia.org/wiki/Pollard 's_p_%E2%88%92_1_algorithm

http://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html

这是从 n 中分解一些东西，但始终找不到 p。np 和 sp 分别来自 numpy 和 scipy。所以 sp.uint64 的内置函数是一个 unsigned long 64 int（因为预期整数的大小），而 np.prod(p) 是列表 p 的累积乘积 pi：

输出找不到 p：

我正在学习 Python，所以这可能是一些简单的错误。power2() 函数使用平方求幂，基本上是一个超大整数的超级充电 pow()。euc_al_i() 就是 gcd。你可以使用任何你喜欢的 gcd()，但是因为我正在学习我想自己做这些。

我试图找出这里出了什么可怕的错误，以至于它甚至无法从相对较小的 n（小至 20 位长度）中找到 p。