[백준] 1124번 : 언더프라임 – JAVA [자바]

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

 

 

 

---

문제

 

 

---

해결 방법

이 문제는 소수 판별 및 소인수분해를 활용한 수 카운팅 문제이다. 다음과 같은 방식으로 해결할 수 있다.

1. B까지의 소수를 구한다.
- 에라토스테네스의 체를 이용하여 B 이하의 모든 소수를 구한다. 에라토스테네스의 체의 대한 자세한 정보는 여기서 확인할 수 있다.

2. 각 숫자의 소인수 개수를 구한다.
- B 이하의 모든 수에 대해 소인수분해를 수행하여 소수 개수를 센다.

3. 소인수 개수가 소수인지 확인하여 카운트한다.
- A부터 B까지의 숫자 중에서 소인수 개수가 소수인 경우를 센다.

이 방법을 사용하면 O(N log log N + N log N)의 시간 복잡도로 문제를 해결할 수 있다.

 

 

 

---

코드 

 

import java.io.*;
import java.util.*;

public class Main {
    static List<Integer> primes;
    static int a;
    static int b;
    static boolean[] isPrime;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        primes = new ArrayList<>();
        isPrime = new boolean[b+1];
        isPrime[0] = isPrime[1] = true;
        getPrimes();
        int count = 0;
        for (int i = a; i <= b; i++) {
            if (!isPrime[getDivisions(i)]) count++;
        }
        System.out.println(count);
    }

    // 에라토스테네스의 체를 이용하여 B 이하의 소수를 구하는 함수
    public static void getPrimes() {
        for (int i = 2; i <= b; i++) {
            if (!isPrime[i]) {
                primes.add(i);
                for (int j = i + i; j <= b; j+=i) {
                    isPrime[j] = true;
                }
            }
        }
    }

    // 특정 숫자의 소인수 개수를 구하는 함수
    public static int getDivisions(int num) {
        if (!isPrime[num]) return 0; // 소수인 경우 바로 반환
        int count = 0;
        while (num != 1) {
            for (int i = 0; i < primes.size(); i++) {
                if (primes.get(i) > num) break;
                if (num % primes.get(i) == 0) {
                    count++;
                    num /= primes.get(i);
                }
            }
        }
        return count;
    }
}

 

 

---

코드 설명

1. 소수 판별 (getPrimes())
- 에라토스테네스의 체를 이용하여 B 이하의 모든 소수를 효율적으로 구한다. 
- 소수 리스트 primes에 저장하여 이후 소인수분해에 활용한다.

2. 소인수 개수 계산 (getDivisions())
- 숫자를 소인수분해하여 사용된 소수의 개수를 구한다.
- 나눠질 때마다 카운트를 증가시키며, 나누는 과정을 반복한다.

3. 언더프라임 개수 확인
- getDivisions(i)를 통해 얻은 소수 개수가 소수인지 확인한다.
- 소수면 카운트를 증가시킨다.

---

시간 복잡도 분석

1. 소수 구하기 (getPrimes())
O(B log log B) (에라토스테네스의 체)

2. 소인수 개수 구하기 (getDivisions())
각 수에 대해 소수 리스트를 탐색하며 나눗셈 수행 → O(B log B)

3. 전체 과정
O(B log log B + B log B) ≈ O(B log B)

100,000 이하의 범위에서는 충분히 빠르게 실행될 수 있다.