# 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.

- First, make a list with all the odd numbers until the integer part of the square root of $ n$.
- Then, add the number 2 to this list because it is a prime number.
- Next, compute the modulo of $ n$ with each element of the list, call it $ p$.
- Divide $n$ by each $p$. If the quotient is an integer, then change $n$ by this quotient.
- 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) |