[BOJ/C++] 1456 거의 소수

에라토스테네스의 체 알고리즘을 이용하여 문제를 해결할 수 있습니다.

입력이 최대 10의 14승 이고 에라토스테네스의 체를 이용하면 제곱근까지만 수행하면 됩니다.

먼저 에라토스테네스의 체를 이용하여 소수를 구해줍니다

이후 모든 소수에 대해서 거듭제곱을 하며 B보다 작거나 같을때까지 A보다 크거나 같으면 count를 증가시킵니다.

// boj g5 1456
// 거의 소수
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

static vector<bool> v;

int main(void)
{
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    long long A, B;
    cin >> A >> B;

    v.resize(sqrt(B)+1);

    v[1]=true;
    for(int i=2; i<=sqrt(B); i++)
    {
        for(int j=2; i*j<=sqrt(B); j++)
            v[i*j]=true;
    }
    
    int count=0;
    for(long long i=2; i<=sqrt(B); i++)
    {
        int k=2;
        if(!v[i])
        {
            while(pow(i,k)<=B)
            {
                if(pow(i,k)>=A)
                    count++;
                k++;
            }   
        }
    }


    cout << count;

    return 0;
}