최적화 팩토링 프로그램

Question

이것은 숫자의 모든 요소를 ​​찾는 데 사용되는 팩터 화 코드입니다.하지만 대략 7 자리가 지나면 프로그램이 느려지 기 시작합니다.

그래서이 프로그램을 최적화하여 숫자를 더 빠르게 factorise 할 수있는 방법이 있는지 궁금합니다.

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

가장 효과적인 최적화는 숫자가 아닌 사소한 요소를 가지고 있으며, 그 중 가장 작은 수의 제곱근보다 작은, 계속 할 필요가없는 경우 있음을 지적하는 것입니다 이 제곱근을지나 루핑.

실제로 가장 작은 요소는 m입니다. 우리는 n = m.p을 가지고 있으며 다른 요소는 p >= m입니다. 그러나 m > √n이면 m.p >= n, 모순. 이 최적화는 속도 업 것을 소수의 처리를

---

주 (복합 것들에 대한이 검색 어쨌든 √n 전에 중지). 그러나 소수의 밀도와 n이 √n보다 훨씬 더 크다는 사실은 그것을 가치있게 만듭니다.

---

또 다른 최적화는 최소 제수가 소수이어야하며 소수의 저장된 테이블을 사용할 수 있다는 점에 유의해야합니다. (10 억 미만의 소수는 5 천 1 백만 미만입니다.) 속도 향상은 눈에 띄지 않습니다.

Answer 2

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