Home / Project Euler / Problem 5 - Smallest multiple

Published: April 28, 2023

Project Euler

Problem 5 - Smallest multiple

Problem

This problem comes from Project Euler 5

Problem

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

The solution involves what we have seen in previous problems: prime factorization. Let’s look at the example given in the problem.

Prime Factorization

Let’s start by performing prime factorization on the numbers 1 to 10

  • 1=11 = 1
  • 2=22 = 2
  • 3=33 = 3
  • 4=2×24 = 2 \times 2
  • 5=55 = 5
  • 6=2×36 = 2 \times 3
  • 7=77 = 7
  • 8=2×2×28 = 2 \times 2 \times 2
  • 9=3×39 = 3 \times 3
  • 10=2×510 = 2 \times 5

Let’s do two things

  1. Ignore any number that have different factors (6 and 10)
  2. Take the first factor from each number, except the numbers we ignored, and multiply them

This is the result of the above operation

1×2×3×2×5×7×2×3=25201 \times 2 \times 3 \times 2 \times 5 \times 7 \times 2 \times 3 = 2520

Hey! The number from the problem popped out!

I won’t lie. I’m not entirely sure I understand why this works; it’s just something I noticed.

Algorithm

This is the solution I programmed

  1. Perform prime factorization on the numbers 1 to 20
  2. For each number, create a set, which will discard repeated factors. This is the same as taking the first factor from each number.
  3. Any set that has more than one member is discarded. This is the same as ignoring numbers that have different factors.
  4. Multiply all the sets

Code

# Project Euler: Problem 5
# Smallest Multiple

import math

primes = [2, 3, 5, 7, 11, 13, 17, 19]
factors = []

for num in range(2, 21):
    list = set()

    # Steps 1 and 2: Perform prime factorization on each number
    # and discard duplicate factors
    for prime in primes:
        while (num % prime == 0):
            num = num / prime
            list.add(prime)

    # Step 3: Discard factorizations with different numbers
    if len(list) == 1:
        factors.append(list.pop())

# Step 4: Multiply all factors
print(math.prod(factors))
// Project Euler: Problem 5
// Smallest Multiple
// Alternate Rust version

use std::collections::HashSet;

fn main() {
    let mut product: i32 = 1;
    let primes = vec![2, 3, 5, 7, 11, 13, 17, 19];

    for i in 2..=20 {
        let mut num = i;
        let mut list = HashSet::new();

        // Steps 1 and 2: Perform prime factorization
        // on each number and discard duplicate factors
        for prime in primes.iter() {
            while num % prime == 0 {
                num = num / prime;
                list.insert(prime);
            }
        }

        // Steps 3 and 4: Discard factorizations with 
        // different numbers and multiply all factors
        if list.len() == 1 {
            let factor: i32 = *Vec::from_iter(list)[0];
            product = product * factor;
        }
    }

    println!("{}", product);
}