[BOJ] 1124 - 언더프라임

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

BOJ - 언더프라임

문제 유형: 수학

문제 난이도: Silver I

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

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

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

 

입력

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

 

2 <= A <= B <= 100000

 

출력

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

 

풀이

에라토스테네스의 체를 이용해서 소수들을 미리 계산해놓는 것이 좋다.

그러고, a부터 b까지 소인수분해한 뒤, 소인수의 개수가 소수인지 아닌지 구하고 소수라면 1씩 누적한다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int a, b;
vector<bool> isPrime;

bool isUnderprime(int x) {
  if (isPrime[x])
    return false;
  int cnt = 0;
  for (int i = 2; i <= x; ++i) {
    if (!isPrime[i])
      continue;
    while (x % i == 0) {
      x /= i;
      cnt++;
    }
  }

  return isPrime[cnt];
}

int main(int argc, char *argv[]) {
  cin >> a >> b;
  isPrime.resize(100001, true);
  isPrime[0] = false;
  isPrime[1] = false;
  for (int i = 2; i <= 100000; ++i) {
    if (!isPrime[i])
      continue;
    int j = i * 2;
    while (j <= 100000) {
      isPrime[j] = false;
      j += i;
    }
  }

  int ans = 0;
  for (int i = a; i <= b; ++i) {
    if (isUnderprime(i))
      ans++;
  }

  cout << ans << "\n";

  return 0;
}