[백준 1124번] 언더프라임 (C++)

문제링크 : https://www.acmicpc.net/problem/1124

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

const int MOD = 1000000007;

int arr[100001];

bool check(int n)
{
    if(n<2) return 0;
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0) return 0;
    }
    return 1;
}

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

    vector<int> prime;
    memset(arr, 1, sizeof(arr)); 
    for(int i=2; i<100001; i++) //미리 소수 체크
    {
        if(arr[i]) 
        {
            prime.push_back(i);
            for(int j=i*2; j<100001; j+=i)
            {
                arr[j]=0;
            }
        }

    }

    for(int i=A; i<=B; i++) //A~B까지 소인수 분해 체크
    {
        int x=i;
        int cnt = 0;
        for(auto j : prime)
        {
            while(x%j==0)
            {
                cnt++;
                x/=j;
            }
            if(x<2) break;
        }
        if(check(cnt)) result++;
    }
    
    cout << result;

    return 0;
}

 

에라스토테네스의 체를 활용해 우선 입력범위 만큼 소수체크를 해준다.

이때 주의할점은 j=i*i가 아니라, j=i*2로 하는 것이다.

j=i*i를 하면 i 값에 따라 int 범위를 벗어나 오버플로우가 발생한다.

따라서 효율성이 약간 떨어지더라도 j=i*2를 선택해주었다.

 

이후로는 A~B까지 각 값에 대해서 미리 판별한 소수에 대해 나누어 떨어지는 지 체크하며 값을 나눠준다.

나눌 때마다 소수 값의 개수를 체크하며, 이렇게 체크한 총 개수가 또 소수인지 체크후 최종 정답 카운트를 하면 된다.