2022-08-25-prime-factorization-11653

• toc {:toc}

문제

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

입력

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

출력

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

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

풀이

1. N을 소수k로 나누어 떨어질 때 k를 출력하면 된다.
2. 루트(N)이하의 수만 사용하는 방식을 생각했으나 while문이 안돌아가는 문제에 봉착.
3. 그러나 while문 이후 N이 0 또는 1이 아니라면 N 또한 소인수다.

#include <iostream>
 
using namespace std;
 
bool is_primeNum(int n);
 
int main()
{
	int N;
	cin >> N;
	for(int i=2; i*i<=N; i++)
	{
		if(is_primeNum(i))
		{
			while(N%i==0)
			{
				cout << i << endl;
				N = N/i;
			}
		}
	}
	if((N!=0)&&(N!=1))
		cout << N << endl;
	
	return 0;
}
 
bool is_primeNum(int n)
{
	int i = 2;
	while(i*i<=n)
	{
		if(n%i==0)
			return false;
		i++;
	}
	return true;
}