优化保理程序

Question

这是我的因式分解代码，用于查找一个数的所有因数，但在大约 7 位数字后，程序开始变慢。

所以我想知道是否有任何方法可以优化此程序以使其更快地分解数字。

number = int(input("Input the whole number here?\n"))
factors = [1]

def factorization():
    global factors
    for i in range(1 , number):
        factor = (number/i)
        try:
            factorInt = int(number/i)
            if factorInt == factor:
                factors.append(factorInt)
        except ValueError:
            pass


factorization()
print(factors)

Answer 1

让我提供一个基于 NumPy 的解决方案。好像挺有效率的：

import numpy as np

def factorize(number):
    n = np.arange(2, np.sqrt(number), dtype=int)
    n2 = number / n
    low = n[n2.astype(int) == n2]
    return np.concatenate((low, number // low,))

factorize(34976237696437)
#array([     71,  155399, 3170053, 492623066147, 225073763,     11033329])])
# 176 msec

Answer 2

最有效的优化是注意到当数字有非平凡的因素时，其中最小的因素小于数字的平方根，并且没有必要继续循环超过这个平方根。

确实，让这个最小的因数为m。我们有 n = m.p，另一个因素是 p >= m。但是如果m > √n，那么m.p >= n，矛盾。

请注意，此优化只会加快素数的处理速度（对于合数，无论如何搜索都会在 √n 之前停止）。但是素数的密度和 n 比 √n 大得多的事实使其绝对值得。

另一个优化是注意最小除数必须是质数，您可以使用存储的 table 个质数。（10亿以下的质数不到5100万。）提速会不太明显。

优化保理程序

Optimising Factoring Program

python

optimization

factors