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

标签 python algorithm binary-search prime-factoring

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

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

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

最佳答案

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

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

关于python - 当因式分解中出现的(短〜)素数列表已知时,有哪些有效的整数因式分解算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21199883/

相关文章:

python - 链表反转算法不起作用

python - Json序列化问题

python - 更新mongo中的字段类型

c# - 版本控制算法

c# - 如何在排序数组中定位一个点?

algorithm - 为什么二分搜索算法适用于这个一维“寻峰”问题?

python - 在 pandas 数据框中删除特定条件下的值

python - 球体表面点的均匀分布?

performance - 最高效率

algorithm - 为什么我在 Scala 中的二进制搜索实现如此缓慢?