[백준 1456번] 거의 소수 (C++)

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

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

ll A, B;

int main() 
{
    cin >> A >> B;

    vector<bool> v(10000001, true); 
    v[0] = v[1] = false;

    for(int i=2; i*i<=10000000; i++) //에라스토테네스의 채
    {
        if(!v[i]) continue;
        for(int j=i*i; j<=10000000; j+=i)
        {
            v[j] = false;
        }
    }

    int cnt = 0;

    for(ll i=2; i<=10000000; i++)
    {
        if(!v[i]) continue;
        ll tmp = i*i;
        while(tmp <= B)
        {
            if(tmp >= A) cnt++; //범위 내 카운트
            if(tmp > B/i) break; //오버플로우 방지
            tmp*=i; //거듭제곱
        }
    }

    cout << cnt;

    return 0;
}

 

에라스토테네스의 체를 활용한 문제이다.

문제 범위에서 B가 최대 10^14이기에 이에 루트 값을 씌운 10^7범위까지 소수를 미리 체크해준다. (n^2 <= B -> n <= sqrt(B))

이후에는 거듭제곱을 하며 범위를 체크하고 카운팅해주면 된다.

 

이때 주의해야 할 점은 오버플로우이다.

tmp에서 이미 i*i를 해서 최대값이 10000000*10000000인데, 여기서 또 i를 곱하기 때문에 10000000를 곱하게 된다.

이 경우 long long 범위 또한 벗어나기 때문에 정상적인 카운팅이 되지 않는다.

따라서 tmp*=i 거듭제곱 계산하기 직전에 범위를 체크해 끊어주어야 한다.