找到约数的数^ 2

Question

我试图解决following problem，我减少到（N！）（！N） 发现的约数的数^ 2

我编码（我没有被指责没有做任何工作），并且它适用于大数量的应用程序，但是由于超时而没有通过所有的测试，我认为我的算法效率不高。

这里是我的想法的轮廓：

1. 任何数字都可以表示为a0^b1*a1^b1*...*an^bn这将有(1 + b1)*(1 + b2)*...*(1 + bn)除数
2. 然后M^2将有(1 + 2b1)*(1 + 2b2)*...*(1 + 2bn)除数
3. 创造出发现的所有因素的函数并将它们保存为散列图
4. 具有通过添加相应键的值来组合两个hashmaps的功能
5. 使用这2个功能，从2到所有的数字迭代到n得到的阶乘
6. 所有除数使用功能从1得到的答案

我认为这个解决方案是非常有效的，但看起来有更好的方法。 任何人都可以给我一个更好的方法吗？

Answer 1

您的问题有一个简单而有效的解决方案。需要注意的是n!是：

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * ... * n 

让我们想想一个主要因素有多少次出现在本产品，例如2。 每隔2出现一次。但每4因素一次出现两次。并且每8因子一次出现三次等。 换句话说，因子2将出现在n!sum(n//(2**e) for e in range(1, n))次。对于任何主要因素k也是如此。

您可以实现此计算有：现在

import itertools as it 

def exp_for_factor_in_factorial(factor, n): 
    total = 0 
    for e in it.count(1): 
     if factor ** e > n: 
      break 
     total += n // factor**e 
    return total 

，为了找到我们需要找到所有素数达n的n!所有的主要因素，这是很容易使用埃拉托色尼完成：

import math 

def sieve(n): 
    nums = [True] * (n+1) 
    nums[:2] = [False]*2 
    nums[4::2] = [False] * math.ceil((n-3)/2) 
    for i in range(3, int((n+1)**.5)+1, 2): 
     if nums[i]: 
      for j in range(i*i, n+1, 2*i): 
       nums[j] = False 
    return [i for i,k in enumerate(nums) if k] 

这使我们能够获得的n!的分解：

def get_factorization_factorial(n): 
    primes = sieve(n) 
    factors = [] 
    for p in primes: 
     factors.append((p, exp_for_factor_in_factorial(p, n))) 
    return factors 

最后，计算除数的数量从因式分解你可以使用你已经提到的公式：

import operator as op 
from functools import reduce 

def get_num_divisors(factorization): 
    return reduce(op.mul, (e+1 for _, e in factorization), 1) 

所以最终的答案可以作为获得：

def divs_of_squared_fact(n): 
    return get_num_divisors((p, 2*e) for p, e in get_factorization_factorial(n)) 

请注意，此解决方案极其比你更好的性能：

In [41]: %%timeit 
    ...: for i in range(2, 1000): 
    ...:  x = divs_of_squared_fact(i) 
    ...: 
1 loops, best of 3: 276 ms per loop 

In [42]: %%timeit 
    ...: for i in range(2, 1000): 
    ...:  x = divisorsOfFactorialSquare(i) 
    ...: 
1 loops, best of 3: 7.89 s per loop 

它能够产生除数的数0在约2ms，而另外一个需要近半秒：

In [47]: %timeit divs_of_squared_fact(5000) 
100 loops, best of 3: 2.07 ms per loop 

In [48]: %timeit divisorsOfFactorialSquare(5000) 
1 loops, best of 3: 439 ms per loop 

好吧，其实答案有不同的渐近复杂性，以便增加参数当差趋于无穷。