[백준-정수론] 14232 보석 도둑

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

• 문제
• 풀이

 

---

문제

문제 내용

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

14232번: 보석 도둑

---

풀이

나의 풀이

- 문제 이해하는 데 시간이 좀 걸렸다.

- 문제 풀이 방법은 주어진 입력 값에 대한 소수 값을 구하는 것이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(bf.readLine());

        // 소수를 저장할 리스트
        ArrayList<Long> primes = new ArrayList<>();

        // i의 제곱은 이미 소수가 아니라는 점을 이용
        for(long i=2; i*i<=n; i++) {
            while (n % i == 0) {
                primes.add(i);
                n /= i; // 소수 발견 시 범위 축소를 위해 i로 나누기
            }
        }
        // 만약, n이 1까지 나눠지지 않았다면 해당 수는 소수임.
        if (n != 1) primes.add(n); 

        System.out.printf("%d\n", primes.size());
        for(long prime : primes) System.out.printf("%d ", prime);
    }
}