DeveloperOC

🔗 문제

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

📌 문제 요약

자연수 X를 소인수분해 했을 때 나오는 소수의 목록의 갯수가 소수인 것을 언더프라임이라 한다.

입력: 첫째 줄에 두 정수 A와 B가 주어진다.
출력: 첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 언더프라임 개수를 출력한다.

💡 접근 방법

재귀함수를 통해 X를 소인수분해 했을 때 나오는 값을 다시 소인수분해 하는 방식으로 접근했다.
P 배열에 해당 인덱스의 소수 목록 갯수를 저장하여 재사용하는 방식으로 구현 했다.

⚠️ 처음에 했던 실수

범위 내에 자연수에 대한 언더프라임 값을 출력할 때
P에 목록의 갯수를 인덱스로 접근하면 될 것 같다고 생각했는데
소인수분해시 해당 소수를 사용하지 않으면 값이 이상하게 나오는 경우를 생각 못했다.

💻 코드

#include <iostream>
using namespace std;

int A, B;

int P[100001];

int GetPrime(int value) {
  int ans = 1;

  if (value == 1)
    return 0;

  if (P[value] > 0)
    return P[value];

  for (int i = 2; i * i <= value; ++i) {
    if (value % i == 0) {
      ans = value / i;
      break;
    }
  }

  P[value]++;
  P[value] += GetPrime(ans);
  return P[value];
}

int main() {
  int ans = 0;
  cin >> A >> B;

  for (int i = A; i <= B; ++i) {
    GetPrime(i);
  }

  for (int i = A; i <= B; ++i) {
    if (GetPrime(P[i]) == 1)
      ans++;
  }

  cout << ans;
  return 0;
}