[백준 / BOJ] C++ 1124 언더프라임

1124번: 언더프라임

 

문제

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

1124번: 언더프라임

 

 

풀이

어떤 정수 N을 소인수분해하면 소수의 목록을 얻을 수 있다. 구한 소수의 목록의 길이가 소수이면 이 정수 N을 언더프라임이라고 한다. 정수 A와 B를 입력받고 A부터 B까지의 수 중 언더프라임의 개수를 세는 문제다.

 

범위가 2 ≤ A ≤ B ≤ 100,000 으로 크지 않기 때문에 에라토스테네스의 체를 이용해 미리 소수를 선별해놓을 수 있다. A부터 B까지 1씩 증가하며 소수로 나누어떨어지면 배열에 소수를 추가하고 수를 소수로 나눈다. 이 과정을 거치면 소인수분해가 되어 배열에 소수의 목록을 얻을 수 있다. isPrime 함수로 배열의 크기가 소수인지 판단하고 참이라면 정답 카운트를 1 증가시킨다. B까지 탐색을 마친 후 카운트를 출력하면 답이다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
  if (n < 2)
    return false;
  for (int i = 2; i * i <= n; i++)
    if (!(n % i))
      return false;
  return true;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  int a, b, ans = 0;
  cin >> a >> b;
  
  // 에라토스테네스의 체
  vector<int> sieve(100001, 1), prime;
  for (int i = 2; i <= 100000; i++)
    if (sieve[i]) {
      prime.push_back(i);
      for (int j = i * 2; j <= 100000; j += i)
        sieve[j] = 0;
    }
    
  for (int i = a; i <= b; i++) {
    vector<int> check;
    int x = i;
    for (int j : prime) {
      while (x % j == 0) {
        check.push_back(j);
        x /= j;
      }
      if (x < 2)
        break;
    }
    if (isPrime(check.size())) // 소인수의 개수가 소수인 경우
      ans++;
  }
  cout << ans;
  return 0;
}