[BOJ] 1124번 언더프라임

🔗 문제

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

📌 문제 요약

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

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

💡 접근 방법

문제 유형: 정수론(소수) + 메모이제이션

문제를 두 단계로 쪼개면 명확해진다.

X를 소인수분해했을 때 나오는 소수의 개수를 구한다 (중복 포함)
그 개수가 소수인지 판정한다

예를 들어 12 = 2 × 2 × 3이므로 소수 목록의 개수는 3이고, 3은 소수이니 12는 언더프라임이다.
8 = 2 × 2 × 2 → 개수 3 → 소수 → 언더프라임.
16 = 2⁴ → 개수 4 → 4는 소수가 아님 → 언더프라임이 아니다.

핵심은 1번을 A부터 B까지 모든 수에 대해 구해야 한다는 점이다.
B가 최대 100,000이라 하나씩 완전히 소인수분해하면 같은 계산이 계속 반복된다.

그래서 이런 성질을 쓴다.

X의 가장 작은 소인수를 p라고 하면
  (X의 소인수 개수) = 1 + (X / p 의 소인수 개수)

한 번에 끝까지 쪼갤 필요 없이 소인수 하나만 떼고 나머지는 이미 구해둔 값을 재활용하면 된다.
재귀함수를 통해 X를 소인수분해 했을 때 나오는 값을 다시 소인수분해 하는 방식으로 접근했고,
P 배열에 해당 인덱스의 소수 목록 갯수를 저장하여 재사용하는 방식으로 구현 했다.

그리고 2번(개수가 소수인지)도 같은 함수를 재사용할 수 있다.
소인수 개수가 1이라는 건 그 수 자체가 소수라는 뜻이기 때문이다.
그래서 GetPrime(P[i]) == 1이면 언더프라임이다.

⚠️ 처음에 했던 실수

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

P[i](= i의 소인수 개수)가 소수인지 판정하려면 P[P[i]]를 봐야 할 것 같지만,
P[P[i]]는 아직 채워져 있지 않을 수 있다.
P[i]는 보통 2~17 정도의 작은 값인데, 입력 범위 A가 그보다 크면
그 작은 인덱스들은 첫 번째 루프에서 한 번도 방문되지 않기 때문이다.

그래서 배열을 직접 읽지 않고 GetPrime(P[i])처럼 함수를 한 번 더 호출해야 한다.
그러면 없는 값은 그 자리에서 계산해서 채워준다.

💻 코드

#include <iostream>
using namespace std;

int A, B;

int P[100001];

// value를 소인수분해했을 때 나오는 소수의 개수(중복 포함)를 반환한다
int GetPrime(int value) {
  int ans = 1;   // 남은 몫. 소인수를 못 찾으면 1로 남는다 = value가 소수

  if (value == 1)
    return 0;    // 1은 소인수가 없다

  if (P[value] > 0)
    return P[value];   // 메모이제이션: 이미 구한 값은 그대로 재사용

  // 가장 작은 소인수 i를 찾는다.
  // i * i <= value 까지만 보면 되는 이유:
  // value가 그 범위에 약수가 없다면 value 자체가 소수다.
  for (int i = 2; i * i <= value; ++i) {
    if (value % i == 0) {
      ans = value / i;   // 소인수 하나를 떼고 남은 몫
      break;             // 가장 작은 것 하나만 필요하므로 즉시 종료
    }
  }

  P[value]++;                  // 방금 뗀 소인수 1개
  P[value] += GetPrime(ans);   // 나머지 몫은 재귀에 맡긴다
  return P[value];
}

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

  // 1단계: 구간의 모든 수에 대해 소인수 개수를 미리 채운다.
  //        재귀 도중 나오는 작은 값들도 함께 메모된다.
  for (int i = A; i <= B; ++i) {
    GetPrime(i);
  }

  // 2단계: 소인수 개수가 '소수'인지 판정.
  //        소인수 개수가 1 == 그 수 자체가 소수라는 뜻이므로 같은 함수를 재사용한다.
  //        P[P[i]]로 직접 읽지 않는 이유는 위 '처음에 했던 실수' 참고.
  for (int i = A; i <= B; ++i) {
    if (GetPrime(P[i]) == 1)
      ans++;
  }

  cout << ans;
  return 0;
}

⏱️ 시간·공간 복잡도

B ≤ 100,000, V = 구간 크기 (B − A + 1)

구간	복잡도	설명
`GetPrime` 1회 (캐시 미스)	O(√value)	가장 작은 소인수를 시행 나눗셈으로 찾는다
`GetPrime` 1회 (캐시 히트)	O(1)	`P[value]`를 그대로 반환
1단계 루프	O(V·√B)	구간의 각 수마다 최악 √B번 나눗셈
2단계 루프	O(V)	`P[i]`는 최대 17 정도라 판정이 거의 공짜
전체 시간	O(V·√B)	최악 약 10⁵ × 316 ≈ 3×10⁷
공간	O(B)	`int P[100001]` ≈ 400KB

재귀 깊이는 log₂(B) 수준이다. 소인수를 뗄 때마다 값이 최소 절반으로 줄기 때문에
100,000이어도 17단계를 넘지 않는다. 스택 걱정은 없다.

최악은 value가 소수일 때다. 이때는 루프가 √value까지 끝까지 돌고도 약수를 못 찾는다.
구간 안의 소수들이 비용을 다 부담하는 구조.

🔀 다른 풀이와 비교

방식	전처리	조회	메모
매번 완전 소인수분해	없음	O(√V) × 분해 횟수	같은 값을 계속 다시 쪼갠다
시행 나눗셈 + 메모이제이션 (이 풀이)	없음	O(√B) (첫 계산만)	구현이 짧다. 소수 판정 재활용이 깔끔
에라토스테네스의 체 + 최소 소인수(SPF) 테이블	O(B log log B)	O(log V)	체를 돌릴 때 “이 수를 처음 지운 소수”를 같이 기록해두는 방식

SPF(Smallest Prime Factor) 테이블을 만들어두면 √를 완전히 없앨 수 있다.

체를 돌리면서 spf[x]가 비어 있으면 현재 소수 p를 적어둔다
→ 소인수 개수 = x를 spf[x]로 계속 나누며 센 횟수 = O(log x)
→ 전체 O(B log log B + V log B)

B가 100,000이라 이 풀이로도 충분히 통과했지만,
B가 10⁷쯤 되는 문제였다면 √ 시행 나눗셈은 버티지 못한다.
“구간 전체를 다 봐야 한다”면 체 쪽이 정석이고, 몇 개만 물어보는 문제라면 시행 나눗셈이 낫다.

DeveloperOC

Contact