백준 11653번 소인수분해

<백준 11653번 소인수분해 - 마포 코딩박>

사용한 알고리즘: 에라토스테네스의 체


입력받은 N의 모든 소인수들을 출력해주는 문제였습니다.
문제풀이는 다음과 같습니다.

(1) N이 최대 10^7이므로 대략 4000까지 에라토스테네스 체로 소인수들을 구해줍니다. (N은 root(N) 이상의 소인수로 나눠지지 않습니다.)

(2) 재귀함수 돌려주면서 구해놓은 소인수중 N을 나누는 수가 있으면 이를 저장하고 다시 N/해당수 를 함수로 넣어주는 식으로 답을 구했습니다.

주의할점은 재귀함수를 돌리고 마지막에 남은 수가 1이 아닌경우 ( 구해놓은 소인수로 나눠지지 않은 경우 ) 이 또한 N의 소인수 이므로 저장해주어야 합니다.

	#include <bits/stdc++.h>
	using namespace std;
	int N;
	vector<int> Prime, ans;
	bool visited[4000];
	void MakeAnswer(int a){
	for(auto now: Prime){
	if(a%now==0){
	ans.push_back(now);
	MakeAnswer(a/now);
	return;
	}
	}
	// 남은 수가 소수이면 이또한 정답으로 넣어줘야해요
	if(a!=1) ans.push_back(a);
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	for (int i = 2; i < 4000; ++i){
	if(visited[i]) continue;
	Prime.push_back(i);
	for (int j = 2*i; j < 4000; j+=i) visited[j] = true;
	}
	cin >> N;
	MakeAnswer(N);
	for(auto A: ans) cout << A << '\n';
	return 0;
	}

view raw BOJ 11163.cpp hosted with ❤ by GitHub