2015. 2. 10. 18:23 Programing/Algorithm
프로젝트 오일러 5번
문제: 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?
문제를 푼 알고리즘이 있는데 코딩으로 적용시키는 것이 까다로워서 일단 알고리즘 설명만 남기도록 하겠습니다.
제가 푼 알고리즘은
문제에서 제시된 2520을 소인수분해 하여 찾았습니다.
2520= 2^3 * 3^2 * 5 * 7
이며, 소인수분해를 보시면 1~10까지 소인수를 조합하여 모든 수를 표현 가능 합니다.
그럼 이 수에 11~20의 소수를 먼저 곱하고
X = 2^3 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19
11~20사이의 수를 표현 가능한지 확인 합니다.
2^4인 16이 표현 되지 못하는군요. 저 윗식에 2를 곱합니다.
X = 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19
소인수를 보시면 1~20의 수 모두 표현이 가능하므로 정답이 되겠습니다.
PS) 해답을 보면 제가 풀은 알고리즘을 예시로 들고 log를 이용하여 새로운 식(일반해?라고 해야할까요)을 정의합니다.
'Programing > Algorithm' 카테고리의 다른 글
프로젝트 오일러 7번 (0) | 2015.02.10 |
---|---|
프로젝트 오일러 6번 (0) | 2015.02.10 |
프로젝트 오일러 4번 (0) | 2015.02.10 |
프로젝트 오일러 3번 (0) | 2015.02.10 |
프로젝트 오일러 2번 (0) | 2015.02.10 |