005. Smallest Multiple (여러 수에 대한 최소공배수 구하기)

 

 

​문제 (English)

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(divisible with no remainder) by all of the numbers from 1 to 20?

 

Answer: 232792560

문제 분석

---

최소공배수를 구하는 문제이다. 

1에서 20까지의 모든 수에 대해서 나누어 떨어지는 가장 작은 수라는 것은, 1에서 20까지의 모든 수에 대한 최소공배수를 구하는 것.

 

최소공배수는 다음과 같이 구해진다.

 

- LCM(a,b) = a * b / GCD(a,b)

 

풀이 1 

---

2에서 20까지 수를 증가시키면서, 최소공배수를 구한다. 

LCM(최소공배수)을 구할 때 사용되는 최대공약수(GCD)는 gcd(a,b) = gcd(a, a%b)를 이용해서 구할 수 있다.

1) 2에서 20까지 i를 증가

2) i까지 구한 lcm 값에다가 i+1과의 lcm을 구하면서 전체 lcm 구한다.

 

코드

#[test]
fn test(){
    assert_eq!(1, answer(1));
    assert_eq!(2, answer(2));
    assert_eq!(6, answer(3));
    assert_eq!(2520, answer(10));

    let s = std::time::Instant::now();
    assert_eq!(232792560, answer(20)); 
    println!("test: {:?}", s.elapsed());
}

#[cfg(test)]
// 2..=n까지에 대해 차례로 lcm 구한다.
fn answer(n: u64) -> u64{
    let mut ans: u64 = 1;
    for i in 2..=n {
        ans = lcm(ans, i);
    }

    return ans;
}

#[cfg(test)]
//use the formula : gcd(a, b) = gcd(a, a%b)
fn gcd(mut a:u64, mut b:u64) -> u64{
    let mut t: u64;
    while b != 0 {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

#[cfg(test)]
fn lcm(a: u64, b: u64) -> u64{
    let ret: u64 = a * b / gcd(a,b);
    return ret;
}

 

풀이 2 

---

풀이 1에서 모든 1..=20까지의 수에 대해 lcm을 구했다. 

그러나, ans % i == 0의 경우는 lcm을 구할 필요 없다. 왜냐면 lcm(a,b)=a, where a%b==0

 

이렇게 하면 수행연산이 좀 줄어든다.

fn answer1(n: u64) -> u64{
    let mut ans: u64 = 1;
    for i in 2..=n {
        if ans % i > 0 { // lcm(a, b) = a, where if a%b=0 따라서 0인경우 수행불필요
            ans = lcm(ans, i);
        }
    }

    return ans;
}

 

풀이 3

---

LCM을 GCD를 이용하지 않고도 구할 수 있다. 

 

2..=7까지의 LCM을 구하는 경우를 보자.

i	2	3	4	5	6	7
LCM	2	6	12	60	60	420

 

LCM(6,4)=12가 되는 경우를 보면, i=4보다 작은 j값을 차례로 6에다 곱해보면서 i로 나눠 떨어질 때의 j가 GCD가 된다.

즉, 

LCM	i	j	(LCM*j)%i	new LCM
6	4	2	(6*2)%4=0	6*2=12

이러한 알고리즘을 코드로 짜면 아래와 같다.

fn answer2(n: u64) -> u64{
    let mut ans: u64 = 1;
    for i in 2..=n{
        if ans % i > 0 { // lcm(a, b) = a, where if a%b=0
            for j in 2..=n { //사실 소수만을 대상으로하는것이 맞으나, 그냥해도 큰 차이는 없겠다.
                if (ans * j) % i == 0 { //i=5, ans=12, j=[2,3,4,5,..]에 대해, 12*5=60만이 60%5=0이다.
                    ans *= j;
                    break;
                }
            }
        }
    }
    return ans;
}

 

총평

---

최대공약수가 뭔지, 최소공배수가 뭔지를 근본적으로 생각해보게 하는 문제이다.

 

전체 소스코드

---

p5.rs 

#[test]
fn test(){
    assert_eq!(1, answer(1));
    assert_eq!(2, answer(2));
    assert_eq!(6, answer(3));
    assert_eq!(2520, answer(10));

    let s = std::time::Instant::now();
    assert_eq!(232792560, answer(20)); 
    println!("test: {:?}", s.elapsed());
}

#[cfg(test)]
// 2..=n까지에 대해 차례로 lcm 구한다.
fn answer(n: u64) -> u64{
    let mut ans: u64 = 1;
    for i in 2..=n {
        ans = lcm(ans, i);
    }

    return ans;
}

#[cfg(test)]
//use the formula : gcd(a, b) = gcd(a, a%b)
fn gcd(mut a:u64, mut b:u64) -> u64{
    let mut t: u64;
    while b != 0 {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

#[cfg(test)]
fn lcm(a: u64, b: u64) -> u64{
    let ret: u64 = a * b / gcd(a,b);
    return ret;
}

//----------------------------------------
// lcm을 구하는 경우의 수를 줄인 버전
#[test]
fn test1(){
    assert_eq!(1, answer1(1));
    assert_eq!(2, answer1(2));
    assert_eq!(6, answer1(3));
    assert_eq!(2520, answer1(10));

    let s = std::time::Instant::now();
    assert_eq!(232792560, answer1(20)); 
    println!("test1: {:?}", s.elapsed());
}

#[cfg(test)]
fn answer1(n: u64) -> u64{
    let mut ans: u64 = 1;
    for i in 2..=n {
        if ans % i > 0 { // lcm(a, b) = a, where if a%b=0 따라서 0인경우 수행불필요
            ans = lcm(ans, i);
        }
    }

    return ans;
}


//----------------------------------------
// lcm을 구하는 것을, 원초적인 방법을 이용
#[test]
fn test2(){
    assert_eq!(1, answer2(1));
    assert_eq!(2, answer2(2));
    assert_eq!(6, answer2(3));
    assert_eq!(2520, answer2(10));

    let s = std::time::Instant::now();
    assert_eq!(232792560, answer2(20)); 
    println!("test2: {:?}", s.elapsed());
}

#[cfg(test)]
fn answer2(n: u64) -> u64{
    let mut ans: u64 = 1;
    for i in 2..=n{
        if ans % i > 0 { // lcm(a, b) = a, where if a%b=0
            for j in 2..=n { //사실 소수만을 대상으로하는것이 맞으나, 그냥해도 큰 차이는 없겠다.
                if (ans * j) % i == 0 { //i=5, ans=12, j=[2,3,4,5,..]에 대해, 12*5=60만이 60%5=0이다.
                    ans *= j;
                    break;
                }
            }
        }
    }
    return ans;
}

 

끝