Largest Prime Factor

Python / Project Euler Problems

# Largest prime factor
#
# The prime factors of 13195 are 5, 7, 13 and 29.
#
# What is the largest prime factor of the number 600851475143?
#
# https://projecteuler.net/problem=3

# test
number = 13195 
result = list()

factor = number - 1
while factor > 1:
    if number % factor == 0:
        # factor
        subfactor = factor - 1
        while subfactor > 1:
            if factor % subfactor == 0:
                break

            subfactor -= 1

        if subfactor == 1:
            result.append(factor)

    factor -= 1

assert(max(result) == 29)

# solution (too slow)
# number = 600851475143
# result = list()

# factor = number - 1
# while factor > 1:
#   if number % factor == 0:
#       # factor
#       subfactor = factor - 1
#       while subfactor > 1:
#           if factor % subfactor == 0:
#               break

#           subfactor -= 1

#       if subfactor == 1:
#           print(factor)
#           result.append(factor)

#   factor -= 1

# print(max(result))

# solution (faster)
import math

number = 600851475143
result = list()

while number % 2 == 0:
    result.append(2)
    number = number / 2

for i in range(3, int(math.sqrt(number)) + 1, 2):
    while number % i == 0:
        result.append(i)
        number = number / i

if number > 2:
    result.append(number)

print(max(result))
# 6857