BOJ 백준온라인져지 11653 소인수분해 풀이

문제 설명

1. 소인수를 오름차순으로 출력하면 된다.

풀이

1. 에라토스테네스의 체를 사용해서 풀었었다. 하지만 소수들을 구할 필요 없이

2. 2 부터 나눠질 때 마다 연산을 하면 된다.

3. 범위는 i * i >= N 으로 하면 된다. 왜냐하면 합성수 m=ab 일 때, a 또는 b 가 루트m 을 넘을 수 없기 때문이다. a, b 는 양의 정수이다.

코드

문제

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

입력

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

출력

N의 인수를 한 줄에 하나씩 증가하는 순서대로 출력한다.

예제 입력 1 

72

예제 출력 1 

2
2
2
3
3

예제 입력 2 

3

예제 출력 2 

3

예제 입력 3 

6

예제 출력 3 

2
3

예제 입력 4 

2

예제 출력 4 

2

예제 입력 5 

9991

예제 출력 5 

97
103

출처