프로젝트 오일러 :: 03번 문제풀이 :: java

문제

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.

예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

600851475143의 소인수 중에서 가장 큰 수를 구하세요.

풀이

우선 어떤 숫자가 소수인지 아닌지를 구분할 수 있는 소수 판별 알고리즘을 작성해보자.

소수의 정의는 다음과 같다.

" 1과 자기 자신 외에 어떠한 숫자와도 나누어 떨어지지 않는 수. "

이러한 사실을 기반으로 소수 판별 알고리즘을 아래와 같이 작성할 수 있다.

/* 소수인경우 true를 리턴 */

private boolean isSosu(long x) {

       boolean isSosu = true;

       if (x == 1 || x == 2)

              return true;

       for (long i = 2; i < x; i++) {

              if (x % i == 0) {

                     isSosu = false;

                     break;

              }

       }

       return isSosu;

}

1또는 2가 입력되는 경우에는 바로 true를 리턴한다.

그 외의 숫자는 2부터 n-1까지의 숫자와 나누어 떨어지는지 확인하고 한번이라도 나누어 떨어지는 경우에는 false를 단 한번도 나눠 떨어지는 경우가 없으면 true를 리턴한다.

-

이제 소수 판별이 가능해졌으니 소인수 분해를 위한 알고리즘을 구현해보자.

소인수분해는 나누어 떨어지는 소수만의 곱으로 숫자를 분해하는 것이다.

따라서 작은 소수부터 n까지의 숫자와 나누어봤을 때 나머지가 0인 소수만 추리면 된다.

이러한 사실을 기반으로 아래와 같이 로직을 구현할 수 있다.

public void solution() {

       long x = 600851475143L;

       /* 마지막 수가 소수가 아닌 경우 분해 작업을 반복. ex) 1029 */

       while(!isSosu(x)) {

              for (long i = 1; i < x; i++) {

                     /* i가 소수이며 해당 숫자와 나눠 떨어지는 경우 나눈값을 다시 저장 */

                     if (isSosu(i) && x % i == 0) {

                           x /= i;

                           System.out.println(i);

                     }

              }

       }

       System.out.println("maximum value is " + x);

}

위 로직은 다음과 같이 동작한다.

1. 1부터 n까지 1씩 증가하는 숫자 i가 소수인가?
   
   
2. 위 명제가 참인 경우, i가 n과 나누어 떨어지는가?
   
   
3. 위 명제가 참인 경우, n/i의 값을 n에 저장, 해당 숫자를 출력
   
   
4. for루프가 끝나면 x값이 소수인지 확인.
   
   
5. 소수가 맞으면 루프 종료, 아니면 "1"부터 다시 시작.

여기서 매번 소인수를 구할 때 마다 n/i 값을 n에 대입하는 이유는 문제가 n까지의 소수가 아닌 소인수 중에 가장 큰 수를 구하는 것이기 때문이다.

해당 작업을 해주지 않으면 불필요한 연산이 매우 많아져 결과를 도출하기까지 시간이 엄청나게 소요된다.

(해당 문제의 경우 정답이 6857이므로 문제의 숫자인 600851475143 - 6857 번의 불필요한 연산이 수행되는 것이다.)

위 코드를 실행해보면 아래와 같이 정답을 구할 수 있다.

~ Epilogue ~

이번 문제의 핵심은 얼마나 효율적인 알고리즘을 작성할 수 있는가에 있는 것 같다. 마지막에 언급한 불필요한 연산의 차이가 엄청나기 때문.

해당 문제에서는 수학적 지식이 필요했으나, 일상 생활에서는 더 다양한 분야의 지식들이 필요할 것이므로 우리는 늘 배우고 익히는것을 게을리 하지 말아야 겠다.

github