[BOJ] 백준 11653 소인수분해

Approach

출처: https://www.acmicpc.net/problem/11653

 

N = 72가 주어졌다고 했을 때

오름차순으로 출력되도록 소인수 분해하는 쉬운 방법은

2, 3, 5, 7, … 순으로 나누다가가 완전히 나누어 떨어질때 까지 반복하는 것이다.

 

• 72 / 2 = 36 → 36 / 2 = 18 → 18 / 2 = 9 ( 「2」로는 더 이상 나누어지지 않음)

    ▶ 「2」 를 세번 출력

• 9 / 3 = 3 → 3 / 3 = 1 ( 「3」으로는 더 이상 나누어지지 않음)

    ▶ 「3」 을 두번 출력

 

C++

#include <iostream>

using namespace std;

int n;

int main()
{
    scanf("%d",&n);
    
    if (n == 1) return 0;
  
    int val = 2;
    while(n>1)
    {
        if(n % val == 0)
        {
            printf("%d\n",val);
            n/=val;
        }
        else
        {
            val++;
        }
    }
}

 

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int idx = 2;
		while(true) {
			if(n == 1) {
				break;
			}
			if(n % idx == 0) {
				System.out.println(idx);
				n = n / idx;
			}else {
				idx++;
			}
		}
	}
}