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

문제 설명

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

풀이

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

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

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

코드

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/11653
	* BOJ 백준온라인져지 11653 소인수분해 풀이
	*/
	public class Main {
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(br.readLine());
	for (int i = 2; i * i <= N; i++) {
	if (N % i == 0) {
	N /= i;
	bw.write(String.valueOf(i--));
	bw.write("\n");
	}
	}
	if (N > 1) bw.write(String.valueOf(N));
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

정수 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

출처