python - 当因式分解中出现的(短〜)素数列表已知时，有哪些有效的整数因式分解算法？

Question

我不是严格意义上的初级程序员，但我没有接受过数学以外的正规教育 - 所以这纯粹是业余爱好，可能是业余的。

我最近自己开发了一个算法来解决这个问题，但我想知道是否有任何相对简单的算法明显更高效/更快？

如果有人要求您确定他们正在考虑的数字(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”表达式。这不是这个问题的核心，我只是想知道如果有人想弄清楚它会是什么。

Answer 1

这就是众所周知的二分搜索，这是一种非常著名的算法，您可以在其中找到各种文档。

它的大 O 复杂度为 O(log N)。