1016

에라토스테네스의 체를 이용하기

 

 

 

 

 

 

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
bool sieve[1000010];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll S,L;
	cin>>S>>L;
	ll ans = 0;
	for(ll i = 2; i <= (ll)sqrt(L); i++){
		if(i*i - S >= 0 && sieve[i*i - S]) continue;
		for(ll j = i * i * (S/(i*i)); j <= L; j+= i * i){
			if(j >= S) sieve[j - S] = true;
		}
	}
	for(ll i = 0; i <= L-S; i++){
		if(!sieve[i]) ans++;
	}
	cout<<ans;
	return 0;
}