Calculating Greatest Prime Factor of Any Number

Question

I needed an efficient way to solve this problem but I wanted a way to calculate the greatest prime factor of any number. Is there a better way? What do you think about it? (I also saw some answers with square roots methods. How does that work?)

I tried recursion and memoization at one point. And I also tried finding all the factors and checking whether they are prime. Eventually, I came up with this.

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

I used @nathancy's work as a starting point and slightly optimized the routines to squeeze some performance out. I imagine in-lining the generator would help more, but as-is, at n=123123589503, this routine runs in:

11.6 ms ± 511 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

vs the original

19.1 ms ± 941 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

def generate_alternating_seq():
    while True:
        yield 2
        yield 4


def greatest_prime_factor_opt(n):
    max_prime = -1

    if n % 2 == 0:
        max_prime = 2 # only perform one assignment
        n /= 2
        while n % 2 == 0:
            n /= 2

    if n % 3 == 0:
        max_prime = 3
        n //= 3
        while n % 3 == 0:
            n //= 3

    g = 5
    seq = generate_alternating_seq()
    sqr = int(math.sqrt(n))
    for k in generate_alternating_seq():
        if n % g == 0:
            max_prime = g
            n //= g
            while n % g == 0:
                n //= g
        g += k
        if g > sqr:
            break

    if n > 2:
        max_prime = n

    return max_prime

Answer 2

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