找到約數的數^ 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 

好吧，其實答案有不同的漸近複雜性，以便增加參數當差趨於無窮。