[알고리즘] 소인수분해

소인수 분해란 숫자n을 소수의 곱으로만 나타낸 것을 소인수 분해라고 합니다.

20의 경우 2,2,5로 소인수 분해를 할 수 있습니다. 이것을 코드로 한번 옮겨 보겠습니다.

 

import java.util.Scanner;
public class Main{
    public static void main(String[] args){

       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       
       for(int i=2;n>1;){
         if(n%i==0){
           System.out.println(i);
           n/=i;
         }else{
           i++;
         }
       }
    } 
}

20을 4x5, 2x10으로 나눌 수 있지만 이는 결국 2x2x5가 됩니다. 이 말은, 소수중에 가장 작은 2로 나눌 수 있을 떄 까지 나누고, 더이상 나눌 수 없을 때 다음 소수로 나눈다는 말입니다.

 

위으 코드에서 i=2부터 n을 나눌 수 있을 때 까지 계속 나누다가 나눌 수 없는 경우 i를 증가하여 다시 n을 i로 나눌 수 있을 때까지 나누게 됩니다. i가 4,6인 경우도 2의 배수이기 떄문에 그 전에 2로 나눌 수 있을 때 까지 모두 나눈 상태이기 때문에 4,6으로 나눌 수 있는 값은 없습니다.