백준 11653 c++ 소인수분해

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

11653번: 소인수분해

---

문제

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

입력

 

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

출력

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

---

#include <iostream>
using namespace std;

int main()
{
	unsigned long long int N;//입력받을 정수
	cin >> N;
//에라토스테네스의 체
	bool prime[10000001];
	for (int i = 0; i < 10000001; i++)
	{
		prime[i] = true;
	}
	prime[1] = false;
	for (int i = 2; i < 10000001; i++)
	{
		for (int j = 2 * i; j < 10000001; j = j + i)
		{
			prime[j] = false;
		}
	}
    
	for (int i = 2; i <= N; i++)
	{
		if (prime[N])//N이 소수면 그대로 출력
		{
			cout << N;
			break;
		}
		if (prime[i] && N % i == 0)//i가 소수고 N을 나눴을 때 나머지가 0이라면
		{
			while (1)//i로 그만 나눠질 때까지 계속 나누고
			{
				if (N % i != 0)
					break;
				else
				{
					cout << i<<'\n';//나눌 때 마다 출력
					N = N / i;
				}
			}
		}
	}
}

---

에라토스테네스의 체를 사용하여 prime소수들을 정의하고 문제를 해결했다. 에라토스테네스의 체를 사용하지 않고도 풀 수 있을 것 같았지만 얼마전에 소수 관련 문제들을 이 알고리즘을 사용해서 푸느라 코드가 길어져도 사용했다.

---

 https://mun-coding.tistory.com/27

백준 6588 c++ 골드바흐의 추측

에라토스테네스의 체 참고