[백준 BOJ] 11653번 소인수분해 (C++/cpp)

문제 설명

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

11653번: 소인수분해

 

접근 방법 - 소수 판별 원리를 이용한 문제

백준의 11653번 문제는 소수를 판별하는 원리를 이용하여 해결해야 하는 문제이다.

해당 문제는, 입력값에 대한 소인수분해 결과를 순차적으로 출력해야 하는 문제이다.

여기서, 소인수분해는 특정 숫자에 대하여 소수들의 곱으로 숫자를 분해하여 나타내는 것을 뜻한다.

그렇기 때문에 이 문제는 소수 판정이 중심이 되는 문제라 볼 수 있는 것이다.

다만 한 가지 팁을 적어보자면, <소수의 배수는 소수가 아니다.>라는 점을 생각해보았을 때, 소수가 아닌 숫자들 아래로는 항상 특정 소수들이 있다는 걸 알 수 있다.

(사실 에라토스테네스의 체 알고리즘을 이용하는 건 줄 알았는데, 풀었던 코드를 보아하니 그 알고리즘을 써도 쓴 게 아니었다 카더라(?))

이에 대한 내용은 아래의 설명과 코드를 확인해보면 조금 더 이해하기 쉬울 것으로 예상된다.

해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 값(n)을 입력받는다.

 

2) 2부터 n까지 하여, 반복문을 통해 아래의 연산을 취한다.

- 현재 탐색값인 i에 대하여, n이 나누어 떨어질 때까지 i를 출력하고 나누도록 한다. (while문 사용)

- 더 이상 나누어 떨어지지 않게 되었다면, 다음 순서의 반복문을 수행한다.

(ex) n=12인 경우

(1) n을 2로 나눈 뒤 출력한다 -> n=6, 2 출력

(2) n을 2로 나눈 뒤 출력한다 -> n=3, 2 출력

(3) n을 3으로 나눈 뒤 출력한다 -> n=1, 3 출력   (반복문 종료)

(이렇게 하면, 소수가 아닌 4로 나누어지지 않고 소수인 2로 2번 나누어 떨어지는 과정을 확인할 수 있다.)

 

3) 2)에서 모든 연산이 수행되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 11653번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		while (n % i == 0) {
			n /= i;
			cout << i << endl;
		}
	}
}

 

제출 결과

(2022.06.01 백준 11653번 문제 제출 결과)