優化分解程序

-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

優化分解程序

回答

相關問題