Code. 프로젝트 오일러. KR 3번. C++

프로젝트 오일러 KR 3번.

가장 큰 소인수 구하기

문제 출처.

http://euler.synap.co.kr/prob_detail.php?id=3

요점.

프로그래밍으로 해당하는 수(600851475143)를 어떻게 소인수 분해 할 것인가가 관점이다.

풀이 방법.

생각 보다 복잡하게 생각 할 필요가 없다.

소인수 분해 해야하는 수(A)와 소인수(B)가 있다.

1) B가 A의 소인수인지 확인한다

 => A % B == 0 인지 확인한다.

2-True) A를 B로 그만 나누어 떨어 질때까지 B로 나눈다.

 => 예를 들어 4 = 2 * 2라는 표현이 가능하다.

     다시 말해 소수가 중복으로 존재가 가능 하다.

     그러므로, 해당 소수로 그만 나누어 떨어 질때 까지 A를 계속 나눈다.

3) B는 다음 소수로 넘어간다.

위가 풀이를 요약해둔 것이다.

이를 코드로 옮겨보면

for (int i = 2; target > 1; i++)

{

    if (target % i == 0)

        while (target % i == 0)

        {

            target /= i;

            cout << i << '\t' << target << endl;

        }

}

이렇게 된다.

뭔가 이상한데....

i가 항상 소수라는 보장이 있나?? 라는 생각이 들 수 있다.

아래의 플로우를 보고 혼자서 생각해보길 권장한다.

예를들어 12 = 2 * 2 * 3이라는 수를 소인수 분해 한다 생각해보자

target이란 변수는 12로 초기화가 되어있다.

1) 12 는 2로 나누어 떨어지니 if문 안으로 들어간다.

  12는 2로 나누어 떨어지니 6이된다.

  6은 또 2로 나누어 떨어지니 3이 된다.

2) 3은 3으로 나누어떨어지니 if문 안으로 들어가 1이된다.

3) target이 1이니 끝이 난다.

즉, 12는 4로 나누어 떨어지지만 이미 앞 과정에서 2라는 소수에 의해 나누어져서, 3이 되었다.

앞 과정에서 소수가 아닌 수는 이미 나누어져 없어진다는 결론이다.

그래서 이런식으로 코딩을 하게되면

마지막에 나오는 출력이 소인수중 가장 큰수가 나타나게 된다.

코드 해석.

#include <iostream> using namespace std; #define myint long long int main() { myint target = 600851475143; for (int i = 2; target > 1; i++) { if (target % i == 0) while (target % i == 0) { target /= i; cout << i << '\t' << target << endl; } } return 0; }

요약.

소인수분해하는 코드를 복잡하게 생각하지말고, 간단히 순차적으로만 나가자.