當因式分解中出現的（短）素數列表是已知的時，有什麼有效的算法可用於因式分解整數？

我並不嚴格是初學者程序員，但我沒有受過數學之外的正式教育 - 所以這純粹是業餘愛好和潛在的業餘愛好。當因式分解中出現的（短）素數列表是已知的時，有什麼有效的算法可用於因式分解整數？

我最近自己開發了一個算法，但我想知道是否有任何相對簡單的算法明顯更高效/更快？

該策略的一個非常粗略的描述是，如果有人要求您確定他們想要的數字在1到100之間，您可以使用的比較：是否大於50？「是」。它是否大於75？「沒有」。它是否大於62.5？「是」。它是否大於68.75？等等。您每次將包含答案的值的範圍減半，直到您找到答案。

（評論）的算法如下（在python）：

import math 

#### <parameters> 

z = (2**28)*(3**45)*(5**21)*(7**22)*(11**41) # (example) number to factor 

Pl = [2, 3, 5, 7, 11] # list of primes in fatorisation (in order) 

#### </parameters> 

def a(z1, k1, p1): # roughly: gives the maximum possible power of p1 (in factorisation of z1), divided by 2^(k1) 
    return int(round(math.log(z1, p1)/2**k1, 0)) 

Fact = [] # this will be the list of powers of the primes in Pl 

for i in range(len(Pl)-1): 
    p = Pl[i] 
    b = a(z, 1, p) 
    k = 2 
    while a(z, k, p) != 0: 
     if z % (p**b) == 0: 
      b += a(z, k, p) 
     else: 
      b -= a(z, k, p) 
     k += 1 
    if z % (p**b) != 0: # the above while loop narrows down to two possible values, this narrows down between those two 
     b -= 1 
    Fact.append(b) 
    z = z/(p**b) 
Fact.append(int(round(math.log(z, Pl[-1]), 0))) 

print(Fact)

另外，我有一點不知道如何去尋找對上述「大O」的表達。這不是這個問題的核心，我只是好奇，如果有人關心弄清楚它會是什麼。

來源

2014-01-18 G. H. Faust

我不知道你的算法在做什麼，很大程度上是因爲變量名稱是無益的。在我看來，僅僅用可能的因素來劃分數字就足夠了;可能性列表使問題比一般因子分解更容易。 – user2357112

這就是所謂的二進制搜索，這是一個非常知名的算法，你可以找到各種各樣的文件。

它具有O(log N)的大O複雜度。

來源

2014-01-18 04:12:14 randomusername

當因式分解中出現的（短）素數列表是已知的時，有什麼有效的算法可用於因式分解整數？

回答

相關問題