在课堂上我们发现了这个编程问题，目前我们不知道如何解决它。
给出正整数
n。已知n = p * q, 其中p和q是素数，p<=q并且|q-k*p|<10^5对于某些给定的正整数k。您必须找到p和q。
输入：
35 1
121 1
1000730021 9
输出：
5 * 7
11 * 11
10007 * 100003
这不是家庭作业，我们只是想解决一些有趣的问题。如果您有一些想法，请在此处发布，以便我们尝试一下，谢谢。
问问题
1667 次
5 回答
2
我已经使用ECM方法来分解大整数。它是已知的最有效的算法之一。如果您想了解该算法的工作原理，那么您有很多阅读工作要做，但如果您想利用它进行研究，有些人已经实现了它。例如，您可以获得以下开源软件包：用于 C/C++ 的GMP-ECM或用于 Python 的Pyecm 。
$ python
>>> import math
>>> import pyecm
>>> n = 1000730021
>>> list(pyecm.factors(n, False, False, 2 * math.log(math.log(n)), 1.0))
[10007, 100003]
于 2010-04-15T18:20:46.217 回答
1
n = p * q
|q-k*p|<10^5
和作为输入给出n。k所以
q-k*p=a
和
-10^5<=a<=10^5
乘以n并代入 nq-k*p=a得到qp*q
q^2-a*q-k*n=0
a求解这个二次方程
-10^5<=a<=10^5`
并检查是否q划分n。求解二次方程可以在多项式时间内完成，求解2*10^5+1方程也是如此。n当然，对于较小的值，以及k对于较大的值，n还有更好的算法k。
正如 ypercube 所提到的，人们只需要检查方程
a^2+4*k*n
是一个正方形。
于 2011-05-15T15:03:00.787 回答
1
对于您在此处谈论的大小的数字，最快的因式分解方法是（可能）使用 Eratosthenes 的筛子生成大约为数字平方根的素数，然后使用试除法来找出哪个（s ) 是除数。
已经为更大的数字发明了相当多的因式分解方法。您可能想在 Google 上搜索“Fermat 分解方法”、“Pollard Rho”、“Brent 方法”、“Lenstra 椭圆曲线”、“多项式二次筛”和“一般数域筛”。我已经按照（大致）复杂性和分解更大数字的能力的升序列出了这些。不过，我是否应该提及通用数字域筛是有待商榷的——虽然它是目前已知的用于分解极大数字的最有效方法，但它只适用于非常大的机器——低于大约 110 位左右，MPQS更快，但要考虑 GNFS 更快的大量数字，
于 2010-04-15T16:25:33.560 回答
-1
n = p * q 和 |qk*p|<10^5，其中 n 和 k 作为输入。因此 qk*p=a，其中 -10^5<=a<=10^5 将 qk*p=a 乘以 q 并将 p*q 替换为 n 得到 q^2-a*qk*n=0。用 -10^5<=a<=10^5 对每个 a 求解这个二次方程，并检查 q 是否除以 n。求解二次方程可以在多项式时间内完成，求解 2*10^5+1 方程也是如此。对于较小的 n 和 k 值，有更好的算法
p 在区间内
[(sqrt(k*n+2500000000)-50000)/k,(sqrt(k*n+2500000000)+50000)/k]
因此，您只能检查 p 的 10^5/k 值。q 在区间内
[sqrt(k*n+2500000000)-50000,sqrt(k*n+2500000000)+50000]
它总是包含大约 10^5 个 inegers
于 2011-05-15T19:19:22.330 回答
-1
您可以使用来自http://qurancode.com的基于 GUI 的 YAFU 版本来尝试更大的示例。YAFU 的主要优点是它的自适应特性，它可以在分解时自动切换算法。使用适用于 Windows 7/8/10 的 GUI 版本确实是最好的和更容易的。
只需单击红色心形包围的黄色 PI 符号 :)
于 2019-11-20T17:48:56.807 回答