Pythonで大きな数字の素因数を取得する方法は？

Question

私は600851475143という最大の素因数を見つけたいと思っています。

ただし、のコードではrangeは無効です。数字が大きすぎます。

どうすればよいですか？それ以上の効率的なアルゴリズムはありますか？

list=[] 
for i in range(1,600851475144): 
    count = 0 
    if 600851475143 % i == 0: 
     for x in range(2,i): 
      if i % x == 0: 
       count+=1 
       print(count) 
     if count == 0: 
      list.append(i) 
     count=0 
print(list) 

Answer 1

これが行います。

def PrimeFactor(n): 
    m = n 
    while n%2==0: 
     n = n//2 
    if n == 1:   # check if only 2 is largest Prime Factor 
     return 2 
    i = 3 
    sqrt = int(m**(0.5)) # loop till square root of number 
    last = 0    # to store last prime Factor i.e. Largest Prime Factor 
    while i <= sqrt : 
     while n%i == 0: 
      n = n//i  # reduce the number by dividing it by it's Prime Factor 
      last = i 
     i+=2 
    if n> last:   # the remaining number(n) is also Factor of number 
     return n 
    else: 
     return last 
print(PrimeFactor(int(input())))