python - 找到小于 sqrt(N) 的 N 的最大约数

Question

实际上，给定一个(可能非常大的)偶数 N，我想找到 N = F * R，其中 gcd(F,R) = 1, F>R，并且 F 尽可能小(因为我'将完全分解 F)。问题的核心是找到最大的除数 R，其中 R < sqrt(N)。

例如，N=36 应该给出 F=9 和 R=4。请注意，R 不一定是素数或素数次幂。请注意，我没有分解 N。对 F 和 R 的唯一限制是它们互质。

这是我快速而天真的版本，它正在运行:

def factor_partial(N):
    for R in xrange(int(math.sqrt(N)),1,-1):
        if N%R == 0 and gcd(R,N/R) == 1:
            return N/R, R

我想象的另一种方法是按递增顺序查找除数，并在此过程中删除所有非除数的倍数。像这样的东西:

def factor_partial(N):
    i = range(2, int(sqrt(N)) + 1)
    while i:
        if N % i[0] != 0:
            remove_multiples(i, i[0]) #without removing i[0]
        else:
            if gcd(i[0], N/i[0]) == 1:
                R = i[0]
        i.pop(0) #remove i[0]

    return N/R, R

我认为这会很慢并且会占用大量内存，但也许如果 i 是一个生成器，它可能会很高效。我没怎么用过发电机。

我可以改进第一个版本吗？第二个版本是否可行(我该怎么做)？有没有更好的完全不同的方法？

在 python、c 或伪代码中寻找答案。

---

这是一个关于数论类(class)的项目。我正在实现基于 Pocklington 的素数测试.虽然我需要一个因式分解算法，但我们还没有研究过任何算法，而且我可能不会使用二次筛之类的算法，它超出了我的类(class)范围。我正在寻求有关所提出问题的具体帮助。

Answer 1

维基百科有一个很好的分解算法列表:http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms

您的第二种方法有效地使用了筛子，并且具有在 N 是某个小素数的倍数时快速减少问题的良好特性。可以通过遍历素数而不是 2..sqrt(n) 的所有可能除数来改进代码。

此外，您可能希望从素性测试开始，以便在进行其他工作之前知道 N 是合数。

你的笔记说你没有分解 N 但问题是相关的。搜索 F 和 R 相当于探索 N 的素因子的非重叠组合。

在N==36的情况下, N 的质因数分解为 2, 2, 3, 3 . F 和 R 的因子必须包括所有这些(因此 F*R==N )并且不能有重叠(因此 GCD(F,R)==1 )。所以 4 和 9 立即出现。

一个更有启发性的例子可能是N==23256 .它的分解是2,2,2,3,3,17,19 .由于 F 和 R 之间不能有重叠，每个素数碱基只能进入两个桶中的一个(即你要么得到所有的两个，要么一个都没有) .因此，我们可以将这些因素分组为 8,9,17,19 .要找到 R，我们需要那些尽可能大但低于 152.49(23256 的平方根)的因子的组合。我们的选择是 {8}、{9}、{8,9}、{8,17} , {8,19}。其中最大的是 8*19也就是152。对应的F是17*19或 153。

上面列出的选择计算为[choice for choice in powerset([8,9,17,19]) if prod(choice) < math.sqrt(N)] .

所以整个程序几乎可以归结为:

prime_factors = factorize(N)      # [2,2,2,3,3,17,19]
clusters = [p**e for p, e in collections.Counter(prime_factors).items()]  # [8,9,17,19]
R = max(prod(group) for group in powerset(clusters) if prod(group) < math.sqrt(N))
F = N // R

powerset只要集合的生成超过 N 的平方根，就可以通过修剪集合的生成来加快搜索速度。

请记住，因式分解的计算成本很高，幂集增长非常快，但它可能比开始原始算法要少得多，原始算法从 N 的平方根开始并向下计算.