找出小于sqrt(N)的N的最大除数

Question

实际上,给定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或pseudocode中寻找答案.

---

这是一个关于数论的课程.我正在实施基于Pocklington的素性测试.虽然我需要一个分解算法,但我们还没有研究过任何一个,我可能不会使用像我的班级范围之外的二次筛子.我正在寻找提出问题的具体帮助.

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

所述幂搜索可以由通过修剪的套产生一旦超过上平方根更快Ñ.

请记住,因子分解在计算上是昂贵的,而且功率增长非常快,但它可能远远少于开始原始算法的工作,原始算法从N的平方根开始并向下工作.