# Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

This solution was a little tricky. The best case scenario is if our number—let’s call it $n$—is a perfect square. In this case, the only admissible prime is the root square of $n$ repeated twice.

## Playing with square numbers

Using this idea, the algorithm goes as follow.

1. First, make a list with all the odd numbers until the integer part of the square root of $n$.
2. Then, add the number 2 to this list because it is a prime number.
3. Next, compute the modulo of $n$ with each element of the list, call it $p$.
4. Divide $n$ by each $p$. If the quotient is an integer, then change $n$ by this quotient.
5. Finally, iterate until $n$ is equal to $1$.

My implementation just works, but of course there is room for improvements. If you have any suggestion please let me know them in the comments.

import math   # One large number number = 600851475143   # The list of prime factors prime_factors = []   # A control variable to # know when we finish we_are_done = False   while not we_are_done: # The best case scenario is if # number = some_prime^2 sqrt_root_number = int(math.sqrt(number))   # Create a list of posible primes # 2, 3, 5, 7, ... seq_divisors = range(3, sqrt_root_number, 2) seq_divisors.insert(0,2)   for factor in seq_divisors: # Checking if divisible if number % factor == 0: # If factor is divisible then change # the number by the quotient number = number / factor # add the prime to the list prime_factors.append(factor) # We're not finished yet! we_are_done = False break else: # There is not more factors we_are_done = True   # Just to not include 1 in the list if number != 1: prime_factors.append(number)   print prime_factors print max(prime_factors)

Go back to the list of problems.