[Project Euler #3][C++] 가장 큰 소인수 구하기

문제3: 가장 큰 소인수 구하기

문제

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

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

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

문제 해결 방법

소인수 분해 알고리즘 을 이용하여 문제를 해결하였다.

• 어떤 수 num를 소인수 분해 하려면 num를 2부터 차례대로 num의 제곱근까지의 숫자로 나누어 떨어지는지 검사하면 된다.
• 플로우 차트를 기반으로 문제를 해결하여도 되지만, 코드가 길어지기 때문에 while 문을 사용하여 문제를 해결하였다.

소스 코드

#include <iostream>
using namespace std;
 
long long num = 600851475143; // 입력받을 숫자
int k = 2;                    // 2부터 1씩 증가                                                                                
 
int main() {
   while (num != 1) {
       if (num % k == 0) {
           num /= k;   // Update
       }
       else {
           k++;
       }
   }
 
    cout << k << endl;
 
    return 0;
}

정답

6857

심화 공부

소인수 분해(Prime Factorization)

합성수를 소수의 곱으로 나타내는 방법을 말한다. 산술의 기본 정리에 의해 모든 양의 정수는 소수의 곱으로 표현하는 방법이 (곱의 순서를 바꾸는 것을 제외하면) 유일하게 존재한다. 그러나 산술의 기본정리는 그 소인수 분해를 하는 방법을 알려주지는 않는다. 단지 존재성을 확인해 줄 뿐이다.

소인수 분해 알고리즘

현대의 전자기 기반 컴퓨터 상에서 소인수 분해에 대한 다항식 시간 알고리즘은 알려져 있지 않다. 단, 이론적인 양자 컴퓨터에서의 다항식 시간 소인수 분해 알고리즘(쇼어의 알고리즘)은 존재한다. 하지만 아직까지 어떤 합성수를 다항 시간 안에 소인수 분해하기는 어려운 문제이며, 소인수분해의 난해함은 RSA와 같은 현대 암호의 핵심적 부분이 된다.

예를 들어 193자리 수(RSA-640)는 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해 되었다.

---

문제 출처 : https://euler.synap.co.kr/problem=3