Problem 005 : Smallest multiple (5%)

link

Description

original

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?

간략해석

1에서 20의 최소공배수를 구하여라.

Idea & Algorithm

naive idea

반복문을 쭉 돌리면서 1부터 수가 나누어떨어지는가를 체크하는 방법이 있지만 이 경우에 최악의 케이스 경우에는 20!까지 연산해야한다.

advanced idea

lcm(a,b,c) = lcm(lcm(a,b),c)을 이용하자.

lcm은 결합법칙이 성립한다. 그렇다면 1부터 쭉 lcm을 연속적으로 계산하면 된다. lcm(a,b) = a*b/gcd(a,b)임을 사용하면 쉽게 풀 수 있다.

최소공배수의 성질

집합 $G$에서 최소공배수에서 어떤 소수 $p$는 $p^e (gcd(\frac{LCM}{p^e}, p^e) = 1)$의 형태로 존재한다. 어렵게 썼지만 그냥 소수 $p$가 $e$개 있다는 것이다.

그리고 이 $e$는 $G$의 원소들 중, $p$를 소인수로 가지는 수 중 가장 많이 포함한 경우 $e$개임을 의미한다.

즉, $G$원소들을 소인수분해해서 각 소인수의 최대개수들의 구해서, 모두 곱해주면 된다.

+ gcd 구하는법

유클리드 호제법을 이용하여 구하면 된다. 이는 projecteuler 시작이라는 post에 올려두었다. 아니면 아래 코드를 참조하면 된다.

source code

20!이 longlong범위이므로 단순 구현으로 첫번째 방법을 사용했다.

#include <stdio.h>
#define ll long long

ll gcd(ll a, ll b){
    if(a%b==0) return b;
    else return gcd(b, a%b);
}

ll lcm(ll a, ll b){
    return (a/gcd(a,b)) * b;
}


int main(){
    ll ans = 1;
    for(ll i = 2; i <= 20 ; i++) ans = lcm(ans,i);
    printf("%lld",ans);
}

Problem 005