[종만북] 가장 간단한 형태의 소인수 분해 알고리즘 - 완전탐색(BruteForce) JAVA

출처 : 4.4 지수시간 알고리즘 - 소인수 분해의 수행시간 (종만북)

코드설명

완전탐색을 활용합니다.

 

소인수 분해 문제에서는 입력으로 주어지는 숫자가 알고리즘의 동작에 직접적인 영향을 미치므로, 숫자가 특정 범위 안에 있다고 가정할 수 없습니다.

 

로직설명입니다.

- 2부터 시작하는 반복문을 통해 n을 가능한 모든 정수로 나누며, 나누어 떨어지는 경우(즉, n % div == 0인 경우) 해당 수(div)를 res 리스트에 추가하고, n을 div로 나눕니다. 이 과정을 n이 1보다 큰 동안 계속 반복합니다.

 

코드를 깔끔하게 if문 안에 n > 1 조건문을 넣어서 코드가 짧아졌다는 점이 흥미로웠습니다.

 

입력 예시 1

60

결과 예시 1

60
 2 2 3 5

 

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		ArrayList<Integer> arr = factor(N);
		for(int value : arr) {
			System.out.print(" "+value);
		}
	}
	
	public static ArrayList<Integer> factor(int n){
		if(n == 1) return new ArrayList<Integer>(Arrays.asList(1));
		ArrayList<Integer> res = new ArrayList<Integer>();
		for(int div = 2; n > 1;div++) {
			while(n % div == 0) {
				n /= div;
				res.add(div);
			}
		}
		return res;
	}
}

 

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		for(int v : factor(N)) {
			System.out.print(" "+ v);
		}
	}
	
	public static ArrayList<Integer> factor(int n){
		//기저사례 0 : n이 1일경우 중단.
		if(n == 1) return new ArrayList<Integer>(Arrays.asList(1));
		//기저사례 1 : 만약 n이 1 이하 일겨우 중단.
		if(n < 1) return new ArrayList<Integer>(Arrays.asList(n));
		
		ArrayList<Integer> res = new ArrayList<Integer>();
		for(int div = 2; n > 1; div++) {
			while(n%div == 0) {
				n /= div;
				res.add(div);
			}
		}
		return res;
	}
	
}