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

11653번 - 소인수분해 

 

<접근법>

처음에는 나누는 수가 무조건 소수여야 한다는 생각에 소수를 먼저 다 걸러내려 했습니다. 

하지만 이 방법은 코드도 길어질 거 같고 시간도 많이 걸릴 거 같아서 포기했습니다...

↓

↓

방법 1)

다음에는 입력받은 수만큼 반복문을 돌려 나눠 떨어지는 수를 출력하면 되겠구나!라고 생각했고,

그다음으로는 루트 함수(sqrt 함수)를 사용해서 반복문을 돌리는 횟수를 줄이기도 했습니다. 

#include <iostream>
#include <cmath>

using namespace std;

int main() {

	int N;

	cin >> N;

	for (int i = 2; i <= sqrt(N); i++) {
		while (N % i == 0) {
			cout << i << endl;
			N /= i;
		}
	}
	if (N != 1) cout << N;

	return 0;
}

 

 

<콘솔창>

 

방법 2) 

마지막으로 시도했던 방법은 N의 값이 1이 될 때까지 while 반복문을 돌리는 방법입니다. 

N이 result의 값으로 나눠 떨어지면 출력을 하고, 그렇지 않으면 result의 값을 1씩 증가시켜 반복문을 실행했습니다. 

#include <iostream>

using namespace std;

int main() {

	int N = 0, result = 2;
	cin >> N;

	while (N != 1) {
		if (N % result == 0) {
			cout << result << endl;
			N /= result;
		}
		else
			result++;
	}

	return 0;
}

 

<콘솔창>

 

 

감사합니다!

 

2021.09.30