Project Euler: Problem #3 – Largest prime factor

largest prime factor

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.

I got a new award! Baby Steps: Solve three problems

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.

Comments

Leave a Reply