Problem 5 "Smallest multiple"

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?

問 5 「最小の倍数」

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.


fn gcd(mut a: u64, mut b: u64) -> u64 {
    assert!(a != 0 && b != 0);
    while b != 0 {
        let r = a % b;
        a = b;
        b = r;
    }
    a
}

fn lcm(a: u64, b: u64) -> u64 {
    a * b / gcd(a, b)
}

fn main() {
    let mut acc = 2u64;
    for n in 3..=20u64 {
        acc = lcm(acc, n);
    }

    println!("{}", acc);
    assert_eq!(acc, 232792560);
}

#[derive(Clone)]
struct Factor {
    prime: u32,
    occurrence: u32,
}

fn increment_occurrence(factors: &mut [Option<Factor>; 20], p: u32) {
    if let Some(f) = factors[p as usize].as_mut() {
        f.occurrence += 1;
        return;
    }
    factors[p as usize] = Some(Factor {
        prime: p,
        occurrence: 1,
    });
}

fn list_factors(mut n: u32) -> [Option<Factor>; 20] {
    assert!(n <= 20);
    let mut factors: [Option<Factor>; 20] = Default::default();
    let mut d = 2u32;
    while n > 1 {
        while n % d == 0 {
            increment_occurrence(&mut factors, d);
            n /= d;
        }
        d += 1;
    }
    factors
}

fn merge(factors: &mut [Option<Factor>; 20], b: &[Option<Factor>; 20]) {
    for it in b.iter().zip(factors.iter_mut()) {
        match it {
            (Some(bf), None) => *it.1 = Some(bf.clone()),
            (Some(bf), Some(f)) if bf.occurrence > f.occurrence => {
                f.occurrence = bf.occurrence
            },
            _ => continue,
        }
    }
}

fn main() {
    let mut factors: [Option<Factor>; 20] = Default::default();
    for n in 2..=20u32 {
        let local_factors = list_factors(n);
        merge(&mut factors, &local_factors);
    }
    let mut acc = 1u32;
    for o in &factors {
        if let Some(f) = o {
            acc *= f.prime.pow(f.occurrence);
        }
    }

    println!("{}", acc);
    assert_eq!(acc, 232792560);
}

package main

import (
	"fmt"
	"log"
)

func gcd(a, b uint64) uint64 {
	if a == 0 || b == 0 {
		log.Fatal("gcd(0) is undefined.")
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func lcm(a, b uint64) uint64 {
	return a * b / gcd(a, b)
}

func Example() {
	acc := uint64(2)
	for n := uint64(3); n <= 20; n++ {
		acc = lcm(acc, n)
	}
	fmt.Println(acc)
	// Output: 232792560
}
→ Go playground 
function assert(condition: any, msg?: string): asserts condition {
  if (!condition) {
    throw new Error(msg);
  }
}

function gcd(a: number, b: number): number {
  assert(Number.isInteger(a) && Number.isInteger(b));
  assert(Math.sign(a) === 1 && Math.sign(b) === 1);
  let t: number;
  while (b != 0) {
    t = Number(a);
    a = b;
    b = t % b;
  }
  return a;
}

function lcm(a: number, b: number): number {
  return a * b / gcd(a, b);
}

let acc = 2;
for (let n = 3; n <= 20; n++) {
  acc = lcm(acc, n);
}
console.log(acc);
assert(acc === 232792560);
→ TypeScript playground