不小於另一個數字的數字的因子數

Question

是否有任何有效的方法來查找不小於另一個數字（比如m）的數字（比如說n）的除數的數量。 n可以高達10^12。 我想過篩算法&然後找到除數的數量。 我的方法檢查所有從m到n的平方根的數字。 但我認爲有另一種方式（高效）來做到這一點。

Answer 1

下面是一個例子程序，計算是大於m n個約數的個數。如果有c個除數，那麼largeDivs（）代碼在時間O（c）中運行。 largeDivs（）也以n表示一個因式分解開始，nset是一對形式對（p_i，k_i）的列表，使得n = Product {p_i ** k_i for i in 1..h}。程序之後會顯示一些輸出示例。 check（）例程用於演示largeDivs（）產生正確的結果。 check（）需要很長時間才能獲得較小的m值。

def largeDivs(n, nset, m): 
    p, k = nset[-1] 
    dd = 0 
    if len(nset) > 1: 
     nn, mm = n/p**k, m 
     for i in range(k+1): 
      dd += largeDivs(nn, nset[:-1], mm) 
      mm = (mm + p-1)/p 
    else: 
     c, v = k+1, 1 
     while v<m and c>0: 
      c, v = c-1, v*p 
     return c 
    return dd 

def check (n,m,s): 
    if m<1: 
     return s 
    c = 0 
    for i in range(m,n+1): 
     if (n%i)==0: 
      c += 1 
    return c 


tset = [(2,3),(3,2),(11,1),(17,1),(23,2)] 
n = s = 1 
for i in tset: 
    s *= 1+i[1] 
    n *= i[0]**i[1] 
print 'n=',n, ' s=',s 
m=0 
for i in range(8): 
    print 'm:', m, '\t', largeDivs(n, tset, m), ' Check:',check(n,m,s) 
    m = 10*m + 5 

輸出示例：

n= 7122456 s= 144 
m: 0 144 Check: 144 
m: 5 140 Check: 140 
m: 55 124 Check: 124 
m: 555 95 Check: 95 
m: 5555  61 Check: 61 
m: 55555 28 Check: 28 
m: 555555 9 Check: 9 
m: 5555555 1 Check: 1 

Answer 2

如果你知道素數因素，很容易找到數字的除數;只是採取所有因素的多重性的所有可能的組合。

對於n小到10^12，試劃應該是一個足夠快的因子分解方法，因爲你只需要檢查潛在的因素高達10^6。

編輯：加入關於「所有可能的組合」的討論以及通過審判劃分的保理。

考慮數24505 = 5 * 13 * 13 * 29，要列舉它的除數，採取一切因素的多重性的所有可能的組合：

5^0 * 13^0 * 29^0 = 1 
5^0 * 13^0 * 29^1 = 29 
5^0 * 13^1 * 29^0 = 13 
5^0 * 13^1 * 29^1 = 377 
5^0 * 13^2 * 29^0 = 169 
5^0 * 13^2 * 29^1 = 4901 
5^1 * 13^0 * 29^0 = 5 
5^1 * 13^0 * 29^1 = 145 
5^1 * 13^1 * 29^0 = 65 
5^1 * 13^1 * 29^1 = 1885 
5^1 * 13^2 * 29^0 = 845 
5^1 * 13^2 * 29^1 = 24505 

它也不難通過對因子的數審判分庭。這是算法，您可以將其轉換爲您最喜歡的語言;它足夠快足夠人數達到10^12：

function factors(n) 
    f = 2 
    while f * f <= n 
     if n % f == 0 
      output f 
      n = n/f 
     else 
      f = f + 1 
    output n 

讓我們來看看24505.最初因式分解˚F是2，但24505％2 = 1，所以˚F增加爲3。然後˚F = 3和˚F = 4也不能劃分ñ，但24505％5 = 0，所以圖5是24505倍，並且ñ減少到24505/5 = 4901現在˚F = 5不變，但未能分配n，同樣是6,7,8,9,10,11和12，但最後4901％13 = 0，因此13是4901的因子（也是24505），並且n減少到4901/13 = 377 。此時f = 13不變，13又是一個除數，這次減少了n = 377，所以輸出13的另一個因子，並且n減少到29.在這一點上13 * 13 = 169大於29，所以退出while循環，輸出最終因子29;此工作，因爲如果N = PQ，然後p或q必須小於的Ñ平方根之一（除非在p和q相等且Ñ的情況下是一個完美的正方形），並且由於我們已經完成了除了29的平方根以外的所有p和q的嘗試劃分，所以它必須是素數，並且因此是最終因子。所以我們看到，24505 = 5 * 13 * 13 * 29

我討論這些類型的算法我essay編程與素數。

Answer 3

它取決於應用程序，但如果性能是這樣的問題，我會使用預生成的哈希表。很明顯，10^12個條目可能不適合（或至少不受歡迎）存儲在內存中，所以我會進行分割測試，直到質數，生成散列表條目僅用於那些第一個不能被其整除的數字素數。

例如，雖然粗製濫造書面和未經考驗的，這應該給你一個想法：

int number = 23456789; 
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 0}; 
int pfactors = 0; 
int* prime = primes; 
float temp; 

// check until we reach the end of the array (0) 
while (prime) 
{ 
    // divide by prime and check if result is integer 
    temp = (float)number/*prime; 
    if (temp == floor(temp)) 
    { 
     // if so, increment count of prime factors and loop (same prime again!) 
     pfactors++; 
     number = (int)temp; 
    } 
    else 
    { 
     // else try the next prime 
     prime++; 
    } 
} 

// finally, rely on hash table magic 
pfactors += pregenerated_hash[number];