这是我的分解代码,用来寻找一个数的所有因子,但在大约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)
让我提供一个基于NumPy的解决方案。似乎效率很高:
最有效的优化方法是注意到当数字有非平凡的因素时,其中最小的因素小于数字的平方根,并且没有必要继续循环通过这个平方根。你知道吗
实际上,让这个最小的因子为
m
。我们有n = m.p
,另一个因素是p >= m
。但是如果m > √n
,那么m.p >= n
,一个矛盾。你知道吗注意,这种优化只会加快素数的处理(对于复合素数,搜索在
√n
之前停止)。但是素数的密度和n
比√n
大得多的事实使它非常有价值。你知道吗另一个优化是注意到最小除数必须是素数,并且可以使用素数存储表。(10亿以下的素数不到5100万)加速将不那么明显。你知道吗
相关问题 更多 >
编程相关推荐