Optimisation du programme d'affacturage

Question

C'est mon code de factorisation qui est utilisé pour trouver tous les facteurs d'un nombre mais après environ 7 chiffres, le programme commence à ralentir. Je me demandais s'il existait une méthode d'optimisation de ce programme pour lui permettre de factoriser les nombres plus rapidement.

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

L'optimisation la plus efficace est en notant que lorsque le nombre a des facteurs non négligeables, et le plus petit d'entre eux est plus petite que la racine carrée du nombre, et il n'y a pas besoin de continuer passant derrière cette racine carrée.

En effet, laissez ce plus petit facteur soit m. Nous avons n = m.p et l'autre facteur est tel que p >= m. Mais si m > √n, alors m.p >= n, une contradiction.

---

Notez que cette optimisation accélère-uniquement le traitement des nombres premiers (pour les composites, la recherche s'arrête avant √n de toute façon). Mais la densité des nombres premiers et le fait que n est beaucoup plus grand que √n le rendent absolument valable.

---

Une autre optimisation est en faisant remarquer que le plus petit diviseur doit être un premier, et vous pouvez utiliser une table stockée de nombres premiers. (Il y a moins de 51 millions d'amorces inférieures à un milliard.) L'accélération sera moins perceptible.

Answer 2

Permettez-moi de vous proposer une solution basée sur NumPy. Il semble tout à fait efficace:

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