46 lines
1.1 KiB
Python
46 lines
1.1 KiB
Python
#!/usr/bin/env python3
|
|
|
|
# The prime factors of 13195 are 5, 7, 13 and 29.
|
|
#
|
|
# What is the largest prime factor of the number 600851475143?
|
|
|
|
from projecteuler import is_prime, timing
|
|
|
|
|
|
# Recursive approach: if num is prime, return num, otherwise
|
|
# recursively look for the largest prime factor of num divided
|
|
# by its prime factors until only the largest remains.
|
|
def max_prime_factor(num: int) -> int:
|
|
# Use function defined in projecteuler.py to check if a number is prime.
|
|
if is_prime(num):
|
|
return num
|
|
|
|
# If num is even, find the largest prime factor of num/2.
|
|
if num % 2 == 0:
|
|
return max_prime_factor(num // 2)
|
|
|
|
i = 3
|
|
|
|
# If num is divisible by i and i is prime, find largest prime factor of num/i.
|
|
while True:
|
|
if num % i == 0:
|
|
if is_prime(i):
|
|
return max_prime_factor(num//i)
|
|
|
|
i = i + 2
|
|
|
|
# Should never get here
|
|
return -1
|
|
|
|
|
|
@timing
|
|
def p003() -> None:
|
|
res = max_prime_factor(600851475143)
|
|
|
|
print('Project Euler, Problem 3')
|
|
print(f'Answer: {res}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p003()
|