python - 计算任何数字的最大素因数

Question

我需要一种有效的方法来解决这个问题，但我想要一种计算任何数字的最大素因数的方法。有没有更好的办法？你怎么看待这件事？ (我还看到了一些使用平方根方法的答案。它是如何工作的？)

我曾经尝试过递归和内存。我还尝试找到所有的因子并检查它们是否是素数。最终，我想出了这个。

def next_prime(num):
    while True:
        num = num+2
        if is_prime(num):
            return num


def is_prime(num):
    for x in range(2, num//2):
        if num % x == 0:
            return False
    return True


def greatest_prime_factor(number):
    list = [2,3,5,7,11,13,17,23,29,31,37,41,43,47,53,59,61,67,71,73,79]
    for y in list:
        print('y = ', y)
        while True:
            print('number = ', number)
            if number == 1:
                return y
            elif number % y == 0:
                number = number//y
                if is_prime(number):
                    return number
            elif y == list[-1]:
                list.append(next_prime(y))
                break
            else:
                break

print('greatest ', greatest_prime_factor(600851475143))

Answer 1

import math 
  
def greatest_prime_factor(n): 
    # Initialize max prime factor 
    max_prime = -1
    
    # Determine the number of 2s that divide n
    while n % 2 == 0: 
        max_prime = 2
        n /= 2     
          
    # n is now odd, iterate only for odd integers 
    for i in range(3, int(math.sqrt(n)) + 1, 2): 
        while n % i == 0: 
            max_prime = i 
            n = n / i 
      
    # Handle case where n is a prime number
    # greater than 2
    if n > 2: 
        max_prime = n 
      
    return int(max_prime) 

n = 25
print(greatest_prime_factor(n)) 
  
n = 123123589503
print(greatest_prime_factor(n)) 

n = 600851475143
print(greatest_prime_factor(n)) 

5

572969

6857