[Codeforces 114E]Double Happiness

这个题嘛，主要是这个神奇的数据范围加大了难度。
首先要知道费马平方和定理：一个奇素数是两个正整数的平方和，那么该奇素数必然满足4k+1的形式（k为整数）。注意：2=1+1，所以这个题不要忽略2.
我们发现：17500的平方与3x10^8差不多大，所以可以发现：将17500以内的素数筛出来得到的素数表可以筛出整个范围内的素数。原因很简单，在此不赘述。
也就是说，第一次筛完后第二次筛素数时就按照第一次筛出来的素数去筛。毕竟我们有一张表了，第一次筛素数是“边筛边找”，第二次就直接筛，懒得找。所以比起边筛边找要快得多。
然后就是这个判断：3x10^8太大，bool存不下，怎么办？
只需来一发bitset就可以了，如果没有，就来两发~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
int l,r,c1,c2;
const int N=300000000;
bitset <N+5> vis;
int ans;
int pri[30000];
vector <int> pri2;
void getpri1(){
	for(int i=2;i<=17500;++i){
		if(!vis[i]){pri[++c1]=i;}
		for(int j=1;j<=c1&&i*pri[j]<=17500;++j){
			vis[i*pri[j]]=1;
			if(
		}
	}
}
void getpri2(){
	for(int i=1;i<=c1;++i){
		int st=l/pri[i];
		if(st*pri[i]<l)st++;
		if(st==1)st++;
		for(int j=st*pri[i];j<=r;j+=pri[i])
			vis[j]=1;
	}
	for(int i=5;i<=r;i+=4){
		if(i<l)continue;
		if(!vis[i])ans++;
	}
}
int main(){
	read(l),read(r);
	getpri1();
	getpri2();
	if(2>=l&&2<=r)ans++;
	printf(
	return 0;
}