6

实际上，给定 N a（可能非常大）偶数整数，我想找到 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 或伪代码中寻找答案。

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

4

3 回答 3

5

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

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

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

你的笔记说你没有考虑 N 但问题是相关的。对F和R的搜索相当于探索N的主要因子的非重叠组合。

在 的情况下， NN==36的素数分解是。F 和 R 的因子必须包括所有这些（使得）并且不能有重叠（使得）。所以 4 和 9 立即出现。2, 2, 3, 3F*R==NGCD(F,R)==1

一个更有启发性的例子可能是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

通过在集合的生成超过N上的平方根时修剪集合的生成，可以更快地进行幂集搜索。

请记住，因式分解在计算上是昂贵的，并且幂集增长非常快，但它可能比从N的平方根开始进行许多除法并向下工作的原始算法开始的工作量要少得多。

于 2011-11-25T18:29:32.747 回答
0

你能得到 N 的素因子分解，然后找到小于 sqrt(N) 的所有素因子的最大乘积组合吗？

例如对于 36，它会发现素数分解是 2*2*3*3。然后你会尝试所有不同的素数组合：

2 = 2
3 = 3
2*2 = 4
2*3 = 6
3*3 = 9
2*2*3 = 12
2*3*3 = 18
2*2*3*3 = 36

你知道这些都是 36 的因数，所以你找到最大的一个，它小于 sqrt(36)，结果是 4。

但是，我真的不明白这比只做你的第一个版本要快得多，除非你已经有了一个现有的素数或素数分解列表，或者一些很棒的素数分解算法，或者你正在做所有这个数字非常大。

但即便如此（回到第一个版本）O(sqrt(n)) 是一个非常快的运行时，并且只需要 O(1) 内存，所以第一个算法可能只是要走的路。我看不出它有多慢，尤其是在现代计算机上的 C 语言中。

于 2011-11-25T19:44:35.307 回答
0 
def factor_partial(N):
    R = int(sqrt(float(N)))
    sieve = [1, 1] + [0] * (R-1)
    for i in xrange(2, R) :
        if sieve[i]==0 :
            j=i*i;
            while j<=R :
                sieve[j]=1
                j = j + i
    primes = [i for i in xrange(R+1) if sieve[i]==0]

    saveN = N
    primepower_divisors = []
    for i in primes :
        if N%i == 0 :
            term = 1
            while N%i == 0 :
                term = term * i
                N = N / i
            primepower_divisors = primepower_divisors + [term]
            if N==1 : break

    largecoprime_divisors = [1]
    for i in primepower_divisors :
        for j in largecoprime_divisors :
            largecoprime_divisors = largecoprime_divisors + [i*j]

    F = min([i for i in largecoprime_divisors if i>R])
    return F, saveN/F

我已经使用筛法计算素数列表（在计算素数列表时可能有很多优化）我们可以使用这样一个事实，即.. 没有素数 p 使得 F%p == 0 和 R%p == 0 。因为 gcd(F, R)=1

于 2011-11-25T19:45:29.017 回答