문제: 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
프로젝트 오일러 5번  (0) 2015.02.10
프로젝트 오일러 4번  (0) 2015.02.10
프로젝트 오일러 3번  (0) 2015.02.10
프로젝트 오일러 2번  (0) 2015.02.10
Posted by thread1525

댓글을 달아 주세요


블로그 이미지
1525번 thread 입니다.
thread1525

공지사항

Yesterday9
Today2
Total6,172

달력

 « |  » 2019.10
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

최근에 달린 댓글

최근에 받은 트랙백

글 보관함