[1456] 거의 소수(C++)

문제

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.
두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

 

 

입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

 

 

출력

첫째 줄에 총 몇 개가 있는지 출력한다.

 

 

해결 방법

에라토스테네스의 채를 이용한 문제이다.
에라토스테네스의 채는 소수를 쉽게 찾는 방법인데, 채에다가 찌꺼기를 걸러내는 것처럼
소수를 찾아나가는 것이 아니라 소수가 아닌 애들을 걸러내는 방식이다.

이렇게 소수 여부를 저장했으면 각 소수의 2배수, 3배수....  중에 A보다 크거나 같고 B보다 작거나 같은 수를 찾으면 된다.

이때 주의해야 할 부분이 있는데 

while(num <= B / i)

바로 이 부분이다.

현재 수가 B보다 작거나 같은지를 판단할 때 대부분 num * i <= B 이런식으로 코딩하겠지만
num 이 계속 커지다보면 num * i가 long long의 범위를 벗어나게 되고, 그럼 B와의 비교가 불가능해지기 때문에 큰 수를 input으로 넣으면 시간초과가 날 것이다.
그래서 num * i 가 long long을 넘지 않게 num * i <= B 를  num <= B / i  이런식으로 바꿔줘야 한다! 

 

 

내 코드

// [1456] 거의 소수
#include <iostream>
#include <vector>
#define MAX 10000001
using namespace std;
typedef long long ll;

ll A, B, ans;
bool isPrime[MAX];
vector<int> primeVec;

void Eratos()
{
    for(int i = 2; i < MAX; i++) isPrime[i] = true; // 처음엔 전부 소수로 초기화
    for(int i = 2; i * i <= MAX; i++) {
		if(isPrime[i]) {
            for(int j = i * i; j < MAX; j += i) {
                isPrime[j] = false;
            }
        }
	}  
}

void getAlmostPrime()
{
    for(int i = 2; i <= MAX; i++) {
        if(isPrime[i]) {
            ll num = i, n = 2;
            while(num <= B / i) { // num * i <= b
                if(A <= num * i) ans++;
                num *= i;
            }
        }
    }
}

int main() 
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    cin >> A >> B;
    Eratos();
    getAlmostPrime();
    cout << ans << '\n';

    return 0;
}