백준 1456번 C++ 풀이

https://www.acmicpc.net/problem/1456

1456번: 거의 소수

시간 제한	메모리 제한	solved.ac 티어
2초	256MB	실버 1

문제

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력

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

출력

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

제한

• 1 ≤ A ≤ B ≤ 1014

---

 소수의 n제곱(n >= 2)의 개수를 구하는 문제. 입력 최대 범위가 10^14까지인데, 이를 그대로 배열로 만들려고 하면 배열이 너무 커서 만들지 못할 것이다. 우리는 적어도 소수의 제곱값 이상을 구해야 하기 때문에, 굳이 10^14까지 만들 필요 없이 10^7까지만 구하면 된다.

 

이를 통해 소수만 뽑아내고, 구간 [A, B]에 존재하는 소수의 n제곱값을 구해야 하는데, 이때 long long범위를 넘어갈 수 있다. 왜냐하면 10^7에 거의 근접한 소수 p가 있다고 하자. p의 제곱은 10^14보다는 작기 때문에 반복문에 들어갈 수 있고, 값도 온전하게 존재한다(long long형이 대략 9.22e+18이기 때문). 하지만 여기서 한번 더 p를 한번 더 곱하게 되면 10^14를 넝어서 대략 10^21에 가까워 질 것이다. 이는 long long형의 범위를 넘어서기 때문에, 이를 막아야 한다. 그러므로 단순히 곱한 후에 비교하면 안되며, b를 소수로 한번 나눈 값을 비교해보면 된다. 

 

아래 코드에서 temp는 n제곱값을, x는 소수값이다. 단순히 temp * x를 b와 비교하면 위의 상황에 맞닥뜨릴수 있기 때문에, 이 식을 조금 비틀어서 temp를 b / x와 비교하면 된다. 이렇게 하면 temp * x가 b보다 작은지 알 수 있으며, 동시에 temp * x가 long long형을 넘어서지 않는다는 것을 보장할 수 있기 때문이다.

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MAX = 10000001;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    vector<ll> prime;
    bool* seive = new bool[MAX];
    fill(seive, seive + MAX, true);
    seive[0] = seive[1] = false;

    for(ll i = 2; i < MAX; i++) {
        if(seive[i]) {
            prime.push_back(i);
            for(ll j = 2; i * j < MAX; j++) {
                seive[i*j] = false; 
            }
        }
    }
    delete[] seive;
    ll a, b;
    ll temp;
    int cnt = 0;

    cin >> a >> b;
    for(const ll& x : prime) {
        temp = x;
        while(temp <= b / x){ temp * x가 b보다 작으면
            temp *= x;
            if (temp >= a) cnt++;
        }
    }
    cout << cnt;
}