优化分解程序

-2

这是我的分解代码，用于查找数字的所有因素，但在大约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)

来源

2017-09-10 Dempsey Palacio

可能不是一个很大的改进，但为什么你在'try'语句中做'number/i'而不是'使用'factor'两次？ – DyZ

你是否研究过这个？你应该先尝试一下。两个简单的优化 - 你不需要检查以上sqrt（数字），你不需要检查2以后的偶数。 – pvg

最有效的优化是指出，当数具有不平凡的因素，而其中最小的比数的平方根小，没有必要继续循环通过这个平方根。

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

注意，这仅优化加速向上素数的处理（复合的，搜索√n之前停止反正）。但是素数的密度和n远大于√n的事实使得它非常值得。

另一个优化是指出最小的除数必须是素数，并且可以使用存储的素数表。（低于10亿的素数低于10亿。）加速将不那么明显。

来源

2017-09-11 08:09:20

让我提供一个基于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

来源

2017-09-10 23:23:24 DyZ

优化分解程序

回答

相关问题