#11653: 소인수분해

백준 11653번: 소인수분해

문제:

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

입력:

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

풀이:

• 이 문제를 풀기 위해 알아야 되는 개념은 에라토스테네스의 체이다. 자세한 설명은 #1929: 소수 구하기 문제 풀이에 나와 있으므로 모른다면 문제도 풀어보고 설명도 읽어보기를 바란다.

• 문제를 풀기 위해서는 우선 n까지 에라토스테네스의 체를 구현한다. 구현을 한 뒤에는 소인수분해를 해주면 된다. 2부터 n까지 모든 수를 확인하면서 n이 나뉘어 1이 될 때까지 확인하면 된다. 2부터 넣어보면서 n과 나누어 떨어지면서 소수인 수를 찾고 나누어주면 된다. 나누어 준 뒤에는 break를 이용하여 다시 2부터 세어주면 된다.

  🧐 i값을 자료형에 저장하여 저장한 i 값부터 세어 주는 방법도 해보았지만 걸리는 시간은 똑같다. 오히려, isPrime 배열을 n의 크기 말고 문제에 N의 최대 크기+1로 선언 해주는게 메모리는 좀 더 쓰지만 시간은 단축 되었다.

코드:

#include <iostream>

using namespace std;

int main(){
	int n;
	//입력 
	cin >> n;
	bool isPrime[n];
	//에라토스테네스의 체 구현
	for(int i=2; i<=n; i++) isPrime[i]=true; //true로 배열 초기화
	for(int i=2; i<=n; i++){
		if(isPrime[i]==false) continue; //이미 false인 값 무시
		for(int j=i+i; j<=n; j+=i) isPrime[j] = false; //배수인 경우 false로 저장 
	}
	//소인수분해
	while(n!=1){
		//2부터 n까지 나눠지는 지 확인 
		for(int i=2; i<=n; i++){ //int i = temp; i값을 저장 해서 시작하는 방법도 있음
			//n이 나누어 떨어지고 소수인 i인 경우 
			if(n%i==0 && isPrime[i]){
				//출력 
				cout<<i<<endl;
				//다음 값을 구하기 위해 n을 i만큼 나누어준다 
				n /= i;
				//다시 2부터 확인하기 위해 for문 탈출 
				break;
			}
		}
	}
}