[BOJ / C++] 1124번 : 언더프라임

문제

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

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

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

입력

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

출력

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

제한

• 2 ≤ A ≤ B ≤ 100,000

Solved.ac 레벨

실버 I

풀이

#include <bits/stdc++.h>
#define MAX 100001

using namespace std;

int primeArray[MAX];
vector<int> primeNum;

void eratos(){
    

    for(int i = 2; i <= MAX; i++){
        primeArray[i] = i;
    }

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

    //ㅁ
    for(int i = 2; i <= MAX; i++){
        if(primeArray[i] == i){
            primeNum.push_back(i);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a, b, ans = 0;
    cin >> a >> b;
    eratos();

    for(int i = a; i <= b; i++) {
        int cnt = 0, num = i;

        for(int j = 0; j < primeNum.size(); j++) {
            while(!(num % primeNum[j])) {
                cnt ++;
                num /= primeNum[j];

                if(num == 1) break;
            }
            if(num == 1) break;
        }
        if(primeArray[cnt] == cnt) ans++;
    }

    cout << ans << "\n";

    return 0;
}

에라토스테네스의 체를 활용하여 문제에서 주어진 최대 범위 내의 소수를 모두 구한 뒤, a와 b 범위 내에서 조건을 만족하는 언더프라임을 판별한 뒤 개수를 카운트해주었다.

 

1124번: 언더프라임