[BOJ] 언더프라임

문제

자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.

어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.

두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.

풀이

해당 범위까지 소인수 분해 후 에 길이를 구해서,
해당 길이에 대한 소수 판별을 계속해서 구하는 것은 시간초과가 발생한다.

따라서 특정 범위까지의 소수 판별 여부를 적어두면, 소수 판별을 반복해서 구할 필요가 없어진다.
따라서 에라토스테네스의 체를 이용하여 boolean 배열에 소수여부를 확인하여 이를 판단하도록 한다.

class Main {
    static boolean[] isPrime;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int A = Integer.parseInt(str[0]);
        int B = Integer.parseInt(str[1]);
        isPrime = new boolean[B + 1];
        getPrime(B);

        int answer = 0;
        for (int i = A; i <= B; i++) {
            int primeLength = getPrimeLength(i);
            if (!isPrime[primeLength] && primeLength != 1) {
                answer++;
            }
        }

        System.out.println(answer);

    }

    static int getPrimeLength(int num) {
        int count = 0;
        int i = 2;
        while (num >= i) {
            if (num % i == 0) {
                num /= i;
                count++;
                continue;
            }
            i++;
        }

        return count;
    }

    static void getPrime(int num) {
        isPrime[0] = true;
        isPrime[1] = true;

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j <= num; j += i) {
                    isPrime[j] = true;
                }
            }
        }
    }

}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EC%96%B8%EB%8D%94%ED%94%84%EB%9D%BC%EC%9E%84