Blog :: Z'Laast

Problem

This problem comes from Project Euler 3

Problem

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

What is the largest prime factor of the number 600851475143 ?

Solution

Every natural number, ℕ, is either prime or can be created using prime numbers. For example, the number 2595 can be created using the prime numbers (factors) 3, 5, and 173. That is,

3 \times 5 \times 173 = 2595

To obtain a list of prime factors for a number $x$ , we must

Create a list of prime numbers
Repeatedly and evenly divide $x$ by those primes until it is no longer possible

Prime Number Generator

To create a list of prime numbers, I chose to create the Sieve of Eratosthenes. We first create a range of numbers starting from 2 and ending at a number we choose, e.g., 2 to 10 000. We start by eliminating all multiples of 2 in our range, then move on to the next number that hasn’t been eliminated. We then eliminate all multiples of that number, and so on and so forth, until we only have primes left.

import math

def soe(n):
    '''Sieve of Eratosethenes. Finds prime numbers'''

    primes = []
    number_list = [True]*(n+1)

    for i in range(2, n+1):
        if number_list[i]:
            primes.append(i)

            # Eliminate multiples. They aren't prime
            for multiple in range(i**2, n+1, i):
                number_list[multiple] = False
    
    return primes

How It Works

Let’s examine the implementation of the sieve.

number_list = [True]*(n+1)

This code doesn’t directly create a list of numbers but instead creates a list of booleans. The list is of length $n + 1$ (n+1 is used to account for the zeroth index).

for i in range(2, n+1):
    if number_list[i]:
        primes.append(i)

The code above iterates over the list, starting at 2, and if the boolean is True, then that index is prime. We can then eliminate the multiples.

# Eliminate multiples. They aren't prime
for multiple in range(i**2, n+1, i):
    number_list[multiple] = False

The above code eliminates all multiples of our prime number.

Example

Let’s say we’re currently at number_list[5]

number_list[5] = True, so it is prime
Eliminate all multiples of 5 by setting them to False
Move on to number_list[6]. This was already eliminated as multiple of number_list[2], so we find it has already been set to False
Move on to number_list[7]. This is True so it is prime
Eliminate all multiples of 7 by setting them to False …

This continues on until we have finished the list.

Largest Prime Factor

To find the largest prime factor of the number 600851475143, we generate our list of prime numbers, then repeatedly evenly divide the number by our prime factors. When we can no longer divide the number (the number equals one), we are done and have our largest prime factor.

Note: I say repeatedly divide, as a number can have multiple of the same prime factor. For example, $27 = 3 \times 3 \times 3$ .

# Project Euler: Problem 3
# Largest Prime Factor

from math import sqrt
from PEF import soe

number = 600851475143
primes = soe(10000)

for prime in primes:
    if (number == 1):
        break

    while (number % prime == 0):
        number = number / prime
        print(prime)

if (number != 1):
    print("Error: Generate larger prime list")

# PEF: Project Euler Functions

import math

def soe(n):
    '''Sieve of Eratosethenes. Finds prime numbers'''

    primes = []
    number_list = [True]*(n+1)

    for i in range(2, n+1):
        if number_list[i]:
            primes.append(i)

            # Eliminate multiples. They aren't prime
            for multiple in range(i**2, n+1, i):
                number_list[multiple] = False
    
    return primes

Project Euler

Problem 3 - Largest prime factor