Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

G1sTagList

Posts List

2012년 2월 13일 월요일

[Project Euler] 3. 가장 큰 소인수 구하기

3. 가장 큰 소인수 구하기

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.

Click

이것도 간단하게....
i를 2부터 나눠떨어지면 계속 나눠주고, 아니면 i증가해주며 간단한 코드로 작성.
<script>
function getMaxPrimeFactor(n){
 var temp = n; 
 for(var i=2; i<temp; i++){
  while (temp % i == 0) temp /= i;  
  if(temp==1) { temp=i; break; }
 }
 return temp;
}
</script>
좀더 복잡하게 해주면 2는 따로 예외처리하여 2로 먼저 다 나눠준다음에
i를 3부터 2씩 증가시키며 하면 loop를 반으로 줄일수도.... 있겠지만 그럴 필요성은 크게 느끼지 않군요.

댓글 2개:

  1. 10000000000 일때 오류가 납니다.

    답글삭제
    답글
    1. 감사합니다. 아주 간단한건데 놓쳤었네요.
      if(temp==1) { temp=i; break; } 한줄 추가했습니다. ^^

      삭제