找出小于sqrt(N)的N的最大约数
实际上，给定一个（可能非常大的）偶数 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 或伪代码的帮助。
这是我在数论课上的一个项目。我正在实现一个基于 Pocklington 的质数测试。虽然我需要一个分解算法，但我们还没有学习过任何相关内容，而且我可能不会使用像二次筛法这样的算法，因为那超出了我课程的范围。我希望能得到关于这个问题的具体帮助。
3 个回答
你能先找出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语言写的时候。
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 和 R，因为它们的最大公约数 gcd(F, R) 是 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之间不能有重叠，每个质数因子只能放入两个桶中的一个（也就是说，你要么全选2，要么一个都不选）。所以，我们可以把因数分组为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的平方根开始进行许多除法的原始算法要轻松得多。