如何優化因子的查找因子

Question

我正在求解的問題的一部分需要查找多個因子的因子。我嘗試過的僞代碼就是這樣。

x = 2 
ans = 1 
while(x < n): # n is given number 
    if(isPrime(x)): 
     count = 0 
     temp = x 
     while(temp < n): 
      count += n/temp 
      temp *= x 
     ans *= (count+1) 
    x += 1 

但根據約束條件，n的值可能高達10^8。我怎樣才能優化它？

Answer 1

這些優化適用於查找主因子和因子的所有因子。

使用篩子，獲取質數列表比檢查每個數字以查看其是否爲素數更容易。新的僞代碼將是：

ans = 0 
foreach(x in primes): 
    if(x>n) break # n is given number 
    temp = x 
    while(temp < n): 
     ans += n/temp 
     temp *= x 

其次，注意內循環計算總和（N/X，N/X^2，N/X^3 ...）這可以被改寫，雖然儲蓄是最小的。

ans = 0 
foreach(x in primes): 
    if(x>n) break # n is given number 
    integer temp = n/x 
    while(temp>0): 
     ans += temp 
     temp /= x