[BOJ]11653번: 소인수분해(java, c++)

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

11653번: 소인수분해

 

import java.io.*;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        try {
            Scanner sc = new Scanner(System.in);
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            
            int num = sc.nextInt();
            
            for (int i = 2; i * i <= num; i++) {
                while (num % i == 0) {
                    bw.write(i+"\n");
                    num = num / i;
                }
            }
            
            if (num > 1) {
                bw.write(num+"\n");
            }
            
            bw.flush();
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

c++소스

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N;
    cin >> N;
    
    // N의 소인수 찾기 (단, N이 소수가 아닐때)
    for (int i = 2; i * i <= N; i++)
    {
        while (N % i == 0)
        {
            cout << i << '\n';
            N /= i;
        }
    }
 
    // 마지막 남은 소수 N 출력
    if (N > 1)
    {
        cout << N;
    }
 
    return 0;
}

 

 

소인수분해 

= 소수인 인수들의 곱으로 표현하기

 

 

TIP1

 

소수 포함 여부를 조사할 때에는, 2부터 √N까지 조사하면 된다. 

 for (int i = 2; i * i <= N; i++)

for문의 종료 조건에 실수 √N을 쓰기보다는 i * i <= N 로 표현하는 것이 좋다. 

컴퓨터에서 실수는 근사값을 나타내기 때문에 정확하지 않다. 

 

 

 

TIP2

 

 N을 나누어 떨어지게 하는 몫 i 를 출력한다.

 

진법 변환 문제와는 다르게, 나머지가 아니라 몫을 출력한다.