[백준] 11653: 소인수분해

SuKong·2020년 8월 9일
0
post-thumbnail

'11653- 소인수분해' 문제로 이동!

👉문제

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

👉입력

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

예시 - 72

👉출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다.

예시 -
2
2
2
3
3


✍내 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();	
		ArrayList<Integer> list = factorization(num);
		for( int i = 0 ; i < list.size() ; i++) {
			System.out.println(list.get(i));
		}
	}
	
	static ArrayList factorization(int num) {
		ArrayList<Integer> list = new ArrayList();
		int divisor = 2;
		while( num != 1) {
			if( num % divisor == 0) {
				list.add(divisor);
				num /= divisor;
			}else divisor++;
		}
		Collections.sort(list);
		return list;
	}
	
}


✍Note

divisor를 2부터 1씩 증가해가고, 숫자는 1이 될때까지 divisor로 나눈다.
나눠질 때마다 소인수들을 저장하는 list에 약수를 add한다.

profile
안녕하세요 🤗

0개의 댓글