Question

How to find the largest prime factor of a number in Python

Answer 1

def largest_prime_factor(n):
    div = 2
    max_p_fact = -1

    while n != 0:
        if n % div != 0:
            div += 1
        else:
            max_p_fact = n
            n //= div  # Integer division
            if n == 1:
                break

    return max_p_fact


print(largest_prime_factor(124))  # 2 x 2 x 31
print(largest_prime_factor(288))  # 2 x 2 x 2 x 2 x 2 x 3 x 3
print(largest_prime_factor(1288)) # 2 x 2 x 2 x 7 x 23
print(largest_prime_factor(100000000)) # 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5


     
'''
run:
     
31
3
23
5
 
'''

 

70+ SQL courses for beginners and professionals

Answer 2

import math

# Returns the largest prime factor of n
def largest_prime_factor(n):
    largest = -1

    # Step 1: Remove all factors of 2
    while n % 2 == 0:
        largest = 2
        n //= 2

    # Step 2: Try odd factors from 3 to sqrt(n)
    i = 3
    limit = math.isqrt(n)
    while i <= limit:
        while n % i == 0:
            largest = i
            n //= i
            limit = math.isqrt(n)  # update limit as n shrinks
        i += 2

    # Step 3: If n is still > 2, it is a prime number
    if n > 2:
        largest = n

    return largest


n1 = 124  # 2 x 2 x 31
n2 = 288  # 2 x 2 x 2 x 2 x 2 x 3 x 3
n3 = 1288  # 2 x 2 x 2 x 7 x 23
n4 = 100000000  # 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
n5 = 600851475143  # 71, 893, 1471, 6857

print("Largest prime factor:", largest_prime_factor(n1))
print("Largest prime factor:", largest_prime_factor(n2))
print("Largest prime factor:", largest_prime_factor(n3))
print("Largest prime factor:", largest_prime_factor(n4))
print("Largest prime factor:", largest_prime_factor(n5))


'''
run:

Largest prime factor: 31
Largest prime factor: 3
Largest prime factor: 23
Largest prime factor: 5
Largest prime factor: 6857

'''

 

70+ SQL courses for beginners and professionals