백준 1124번 언더프라임 풀이

문제 설명

• X가 언더프라임이기 위한 조건은 소인수 분해 했을 때, 나오는 소수의 개수가 소수일 때
• A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 언더프라임의 개수를 출력

문제를 보고 든 생각

• 소수를 보고 에라토스테네스의 채를 떠올렸다.
• 에라토스테네스의 채는 하나의 수를 판정하기는 오래걸리지만 여러 개의 수를 판정하기는 빠르다.
• 소인수분해를 어떻게 할까

풀이 간단 설명

1. primeFac 배열에 나누어 떨어지는 가장 작은 소수를 넣었다.
2. nPrime 배열에 소수면 false, 소수가 아니면 true를 넣었다.
3. factors 함수에서 소인수 분해한 결과를 vector<int>로 반환했다.
4. factors 함수의 크기가 nPrime에서 false가 나오면 언더프라임으로 간주했다.

코드

#include <iostream>
#include <vector>
#include <cmath>

#define MAX_N 100005

using namespace std;

int primeFac[MAX_N];
bool nPrime[MAX_N];
int A, B;

void eratosthenes(){
  primeFac[0] = primeFac[1] = 1;

  for(int i=2; i<MAX_N; ++i){
    primeFac[i] = i;
  }
  nPrime[0] = nPrime[1] = true;
  for(int i=2; i*i<MAX_N; ++i){
    for(int j=i*2; j<MAX_N; j += i){
      nPrime[j] = true;
    }
  }

  for(int i=2; i*i<MAX_N; ++i){
    if(primeFac[i] == i){
      for(int j=i*i; j<MAX_N; j += i){
        if(primeFac[j] == j){
          primeFac[j] = i;
        }
      }
    }
  }
}

vector<int> factors(int n){
  vector<int> ret;
  while(n > 1){
    ret.push_back(primeFac[n]);
    n /= primeFac[n];
  }

  return ret;
}

int solve(int n){
  eratosthenes();
  int ret = 0;
  while(n <= B){
    vector<int> facs = factors(n++);
    if(!nPrime[(int)facs.size()]){
      ++ret;
    }
  }
  
  return ret;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> A >> B;
  cout << solve(A);
  
  return 0;
}