백준 - 소인수분해(11653)

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

11653번: 소인수분해

 

소인수분해

 

주어진 숫자를 소인수 분해하여 소수로 나누어지는 수들을 나열하는 문제이다.

소수로 나눗셈이 가능한지를 알아야 하므로 

소수를 구해야한다.

 

소수를 구해 나누어 질 때까지 나누고

나누어지지 않는다면 다음소수로 넘어간다.

 

아래는 제출한 코드입니다.

 

#include <iostream>
using namespace std;

int arr[10000001];

void getPrime()
{
	arr[1] = 0;
	for (int i = 2; i*i < 1000; i++)
	{
		for (int j = i+i; j <= 1000; j += i)
		{
			if (arr[j] == 1) arr[j] = 0;
		}
	}
}
int main(void)
{
	int n;
	for (int i = 1; i < 10000001; ++i) arr[i] = 1;
	cin >> n;
	int div;
	for (int i = 2; i < 10000001; ++i)
	{
		if (n == 1) break;
		if (arr[i] != 1) continue;
		div = i;
		while (1)
		{
			if (n % div == 0)
			{
				cout << div << endl;
				n /= div;
			}
			else
			{
				break;
			}
		}
	}
}