The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143
This problem deals with the fascinating problem of prime numbers factorization, which is considered a hard problem. So hard that our current cryptography schemes rely on this property.
This is my solution:
A few comments:
- The first function (
is_prime) is a simple trial division to determine whether a given number is prime. There are cleverer algorithms to find prime numbers: see for example here. For an interesting discussion you can also have a look at The Genuine Sieve of Erathostenes by Melissa O'Neill.
- The second function uses comprehension to create the list of primes which are factors for the input value. At the end we simply return the biggest factor.