3: Largest prime factor#

Description

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

What is the largest prime factor of the number 600851475143?

Submit your answer

Your Solution#

Lunch this notebook and try to create your own solution!

Tip: look for the launch button (🚀) in the top right corner!

def problem3(N): # N = number to be factorised
    # Try your solution here
    return solution

# Testing:
unittest.main(argv=[''], verbosity=2,exit=False)

# Printing Project Euler Solution
# print(problem3(600851475143))

My solution#

Spoiler Alert!!

See my solution bellow

Every number can be factorised in a primes number combination.

So in my solution I will:

  • start by trying to divide the input number by the smallest prime possible

  • only consider divisions without remainder: if the result of division has a remainder, then the number is either not a factor or not a prime.

  • whenever possible, the number will be divided and its updated value will be used in the next iteration

  • the process will be repeated until the number has been factored to 1

  • the last divisor will be the largest prime factor

Using this approach, the code will run fast even for huge numbers.

def problem3(N):
    i = 2 # first prime
    while (N > 1.0): # test if the number was factored to 1
        if N % i == 0: # check remainder
            N /= i # update the value
        else:
            i += 1 # try a new divisor
    return i

# Testing
unittest.main(argv=[''], verbosity=2,exit=False)

Add main question:

# Printing Project Euler Solution
problem3(600851475143)

6857