[CodeForces][质数][筛法] CF113C Double Happiness

费马二平方定理
知道这个这题就完了
注意范围极大需要用 bitset

代码：

# include <iostream>
# include <cstdio>
# include <bitset>
// # define int long long
# define MAXN 300000005

std::bitset<MAXN>notPrime;
int prime[20000005], cntP;

signed main(){
	int l, r;

	scanf("%d%d", &l, &r);
	
	// for(int i = 2; i <= r; i++){
	// 	if(!notPrime[i]){
	// 		for(int j = i; (long long)(j * i) <= r; j++){
	// 			// std::cout<<i*j<<' ';
	// 			notPrime[i*j] = 1;
	// 		}
	// 	}
	// }

	for(int i = 2; i <= r; i++){
		if(!notPrime[i]){
			prime[++cntP] = i;
		}
		for(int j = 1; j <= cntP && 1ll * prime[j] * i <= (long long)3e8; j++){
			notPrime[i*prime[j]] = 1;
			if(!(i % prime[j])){
				break;
			}
		}
	}

	// puts("FUCK");

	int ans = 0;
	for(int i = 1; i <= cntP; i++){
		if(l <= prime[i] && prime[i] <= r && (!((prime[i]-1)%4))){
			ans++;
		}
	}

	if(l <= 2 && 2 <= r){
		ans++;
	}

	printf("%d", ans);

	return 0;
}