[BOJ] 1124 언더프라임 - JAVA

1. 문제

1124번: 언더프라임

자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.
어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.
두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.

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

2 ≤ A ≤ B ≤ 100,000

---

2. 풀이

1.  먼저 소수를 전부 구한다. 소수면 false, 소수가 아니면 true를 저장한다.

2.  소수를 구하면서 소수의 배수에 해당 소수로 몇 번 나눠지는지도 저장한다.

3.  A와 B를 입력받고 그 사이의 숫자 카운트가 소수라면 결과값+1한다.

4.  답을 출력한다.

boolean[] prime = new boolean[100001];
int[] count = new int[100001];
prime[0] = prime[1] = true;
for(int i=2;i<100001;i++){
   if(prime[i]) continue;
   for(int j=i+i;j<100001;j+=i){
      prime[j] = true;
      int tmp = j;
      while(tmp%i==0){
         tmp/=i;
         count[j]++;
      }
   }
}
StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());

int res = 0;
for(int i=A;i<=B;i++){
   if(!prime[count[i]]) res++;
}

System.out.println(res);

---

3. 결과

소수를 구할 때 같이 카운트를 세지 않고 따로따로 셌더니 시간이 엄청 많이 걸렸다. 수정후에는 시간이 많이 줄었다.