Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 2월 14일 화요일

[Project Euler] 5. 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

5. 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수
1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?
Click
1~20까지 최소공배수를 구하는 문제이죠.
유클리드 알고리즘을 이용해 두 수의 최소 공배수를 구하고 그 수와 다른 수의 최소 공배수를 구하는 방식으로 구했습니다.
유클리드 알고리즘은...
1. 입력으로 두 수 m,n(m>n)이 들어온다. 2. n가 0이라면, m를 출력하고 알고리즘을 종료한다. 3. n가 m를 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다. 4. 그렇지 않으면, m를 n로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3으로 돌아온다.
위와 같구요. 이를 이용해서...
<script>
/** 유클리드 알고리즘을 통해 최대 공약수와 최소 공배수를 구함. **/
function euclid(a,b){
 if (b == 0) return a;
 return euclid(b, a % b);
}
/* 최대 공약수 */
function gcd(a,b){
 return euclid(Math.max(a,b),Math.min(a,b));
}
/* 최소 공배수 */
function lcm(a,b){
 return (a*b) / gcd(a, b);
}
/* 1~n까지의 최소 공배수 */
function getNumsLcm(n){
 var temp = 2;
 for(var i=3; i<=n; i++)
  temp = lcm(temp,i);
 return temp;
}
</script>
위와 같이 구현합니다.

댓글 4개:

  1. 잘보구 갑니다 ㅎㅎ
    근데 궁금한게 왜 19번 라인에서 i<n 이죠?
    i<=n 으로 하면 잘못된건가요?

    답글삭제
    답글
    1. 지적 감사합니다. 20의 경우 소수가 아니기때문에 구지 20까지 넣어서 할 필요는 없지만. 소수를 입력하면 i<=n 으로 처리하는게 맞겠네요.
      수정하겠습니다.

      삭제
  2. 10입력하고 돌리면 2520이 나와야되는거아닌가요

    답글삭제
    답글
    1. 아... 이게 왜 이럴까요;;;
      홍승진 님 댓글 보고 소스 수정할때 다른부분을 건드린거 같네요... 현재 다시 수정하여 정상 동작할겁니다.
      댓글 감사합니다. ^^

      삭제