[BOJ-11653][C++] 소인수분해

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

 

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

예제 입력 1 

72

 

예제 출력 1 

2
2
2
3
3

 

예제 입력 2

3

 

예제 출력 2

3

 

예제 입력 3 

6

 

예제 출력 3 

2
3

 

예제 입력 4 

2

 

예제 출력 4 

2

 

예제 입력 5 

9991

 

예제 출력 5 

97
103

 

알고리즘 분류

• 수학
• 정수론
• 소수 판정

 

문제 출처

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

문제 해결 방법

• 소인수 분해 알고리즘을 이용하여 문제를 해결하였다.
  • 소인수 분해(Prime Factorization) : 숫자를 1보다 큰 자연수인 소인수(소수인 인수)들만의 곱으로 표현하는 것
  • 일단 1이 아닌 2부터 시작하는 것이 핵심이며, 2로 나누지 못할 경우 2에서 하나씩 증가시켜주면서 나누어지는지 체크해주면 된다.

 

코드

#include <iostream>
using namespace std;

void factorize(int n) {
    int factor = 2;    // 시작 값

    while (factor <= n) {
        if (n % factor == 0) {
            cout << factor << '\n';
            n /= factor;
        }
        else {
            factor++;
        }
    }
}

int N;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    factorize(N);

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [기본 수학 2]
• 브론즈I