백준 1456 거의 소수 C++

간단한 해설

 

A와 B사이의 소수의 제곱수들을 구하면 된다.

 

이 때, A와 B가 10^14승까지 될 수 있어서 별 생각 없이 코드를 작성하다 보면 long long형의 범위를 초과할 수 있다.

 

1부터 10^14 사이의 제곱수들을 파악하면 되는 것이므로, 10^7까지의 소수만 계산하면 된다.[sqrt(10^14)]

 

그런데, 막상 A와 B 사이의 제곱수들을 파악할 때도 오버플로우가 발생할 수 있다.

 

다음과 같은 반례가 존재한다.

입력
1 100000000000000

출력
670121

 

현재 제곱수 값 x 소수 가 overflow될 수 있는 가능성이 있기에,

B / 현재 제곱수 값 < 소수 이면 반복문을 탈출하도록 overflow를 없애는 방향으로 가면 된다.

 

답

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define ll long long
using namespace std;
vector<bool> isPrime;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	ll a,b;
	cin>>a>>b;
	isPrime.resize(10000001LL,true);
	isPrime[0]=isPrime[1]=false;
	for(ll i=2;i<=10000000LL;++i){
		if(isPrime[i]){
			for(ll j=i*i;j<=10000000LL;j+=i){
				isPrime[j]=false;
			}
		}
	}
	ll ans=0;
	for(ll i=2;i<=min(10000000LL,b);++i){
		if(isPrime[i]){
			for(ll j=i*i;j<=b;j*=i){
				if(j<a) continue;
				++ans;
				if(b/j<i) break;
			}
		}
	}
	cout<<ans;
}