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

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

 

 

 

 

#문제 해결 방법

 

우선 문제를 살펴 봤을 때

 

소수를 에라토스테네스의 체로 구한다는 생각은 쉽게 할 수 있다.

 

그리고 거의 소수를 (소수의 n제곱) 을 구하는건

딱히 추가적으로 빠른 방법이 없다 생각이 되어서

브루트 포스로 풀어야 겠다는 생각이 먼저 든다.

 

 

그래서 에라토스테네스로

루트 b 까지의 소수를 구하는데

이유는

거의 소수는 소수의 n 제곱이라

루트 b 이상의 소수는 필요 없기 때문이다

    ll limit = sqrt(b) + 1;
    vector<bool> is_prime(limit + 1, true);
    vector<ll> primes;

 

그리고 구한 소수들을 계속 제곱해 가면서 b를 넘지 않고

a 보다 크다면 거의소수를 찾은 것이다.

 

    int count = 0;
    for (ll i : primes) {
        ll temp = i*i;

        while (temp <= b) {
            if (temp >= a) {
                count++;
            }
            if (temp > b /i) break; // 오버플로우 방지
            temp *= i;
        }

    }

 

여기서 주의 할 것은 오버플로우 방지를 하지 않는다면 

틀리니까 오버플로우 방지를 주의하자 

 

#전체 코드

#include <iostream>
#include <string>
#include <istream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;

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

    ll a, b;
    cin >> a >> b;


    ll limit = sqrt(b) + 1;
    vector<bool> is_prime(limit + 1, true);
    vector<ll> primes;

    // 에라토스테네스의 체로 sqrt(b)까지의 소수를 구함
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i <= limit; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }

    int count = 0;
    for (ll i : primes) {
        ll temp = i*i;

        while (temp <= b) {
            if (temp >= a) {
                count++;
            }
            if (temp > b /i) break; // 오버플로우 방지
            temp *= i;
        }

    }

    cout << count << '\n';

    return 0;
}