[백준 자바] 1124번(언더프라임) - 소인수 개수가 소수인 수

실버 1

문제

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

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

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

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 언더프라임 개수를 출력한다.

제한

• 2 ≤ A ≤ B ≤ 100,000

---

 

에라토스테네스의 체를 사용하여 소수를 판별하고 각 숫자의 소인수를 세어 그 개수가 소수인지 확인한다.

i = 2~n의 제곱근을 반복하여 i가 소수일 때 num을 i로 나누어 가면서 count를 증가시킨다.

반복이 끝나고 남은 num이 1보다 크면 이는 마지막 남은 소수이므로 count를 증가시킨다.

count가 소수인 경우 result를 증가시킨다.

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

public class Main1124 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int A = Integer.parseInt(st.nextToken());
    int B = Integer.parseInt(st.nextToken());

    boolean[] primes = sieveOfEratosthenes(B);

    int result = 0;

    for (int n = A; n <= B; n++) {
      int count = 0;
      int num = n;
      for (int i = 2; i * i <= n; i++)
        if (!primes[i])
          while (num % i == 0) {
            count++;
            num /= i;
          }
      
      if (num > 1)
        count++;
      if (!primes[count])
        result++;
    }

    bw.write(String.valueOf(result));

    bw.flush();
    br.close();
    bw.close();
  }

  static boolean[] sieveOfEratosthenes(int max) {
    boolean[] isPrime = new boolean[max + 1];
    isPrime[0] = isPrime[1] = true;

    for (int i = 2; i * i <= max; i++)
      if (!isPrime[i])
        for (int j = i * i; j <= max; j += i)
          isPrime[j] = true;

    return isPrime;
  }
}