此题难点有三：
1.是素数且是平方数的和的形式的数有哪些？
费马二平方定理：除了2这个特殊的素数，所有的素数都可以分两类：被4除余1的素数。 第二类则是被4除余3的素数。第一类素数都能表示为两个整数的平方和，第二类都不能。
因此此题可以转化为[L , R ]中有多少数是除以4余3的。
2.数据范围3e8
普通的数组是明显开不下的。考虑用bitset代替普通数组处理出is_prime。
3.怎么筛。
POJ有一道经典题介绍了经典办法：素数二次筛选。
先处理出 小于等于SQRT(R)的素数。然后用这个区间里的素数的倍数筛掉[L,R]里的合数。
此题正是这三者的结合。
CF 2200分，number theory
bitset<maxn> is_prime; int main() { int l, r; l = readint(), r = readint(); is_prime.set(); for (int i = 3; i * i <= r; i += 2) if (is_prime[i]) for (int j = i * i; j <= r; j += 2 * i) is_prime[j] = false; int res = (l <= 2 && r >= 2); for (int i = 5; i <= r; i += 4) { if (i >= l && is_prime[i]) res++; } printf("%d ", res); }