[BOJ] 거의 소수 - Compy's Blog

거의 소수 #

TimeLimit	MemoryLimit	Condition	TAG
2s	256MB	(1 ≤ A ≤ B ≤ 1e14)	Math(수학), 에라토스테네스의 체, 소수판별

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

아니 문제는 딱히 할 말이 없어요.. 그대로 나와 있기 때문에 하지만 여기서 기본 구현은 쉬워서 50%까지는 뚫는데 거기서 틀려서 뭐지 싶습니다.

이때 잘 보시면 overflow가 발생한다는 것을 알 수 있는데요 저는 이걸 바로 못 발견해서 진짜 많이 당황했습니다. 하지만 이후에 바꿔서 잘 체크해서 넘겨서 AC를 받았네요

진짜 매번 overflow를 조심해야지 했는데 또 이렇게 하는 것을 보니 아직도 많이 부족하네요! 열심히 PS 해야겠습니다. 여러분들도 즐거운 PS 하세용!!

정답 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;

ll a, b;

bool visited[(ll) 1e7+1];
vector<ll> primes;


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

    
    
    
    for(ll i = 2; i < 1e7; i++){
        if(visited[i]) continue;
        for(ll current = i; current <= 1e7; current+=i) visited[current] = true;
        primes.push_back(i);
    }
    
    
    int result = 0;
    for(ll prime : primes){
        ll current = prime*prime;
        while(current <= b){
            result+=(current >= a);
            if(current > b/prime) break;
            current*=prime;
        }
    }

    cout << result;
    return 0;
}

거의 소수#

거의 소수 #