题目链接：
LightOJ 1197 Help Hanzo
题意：
给出区间左右端点[a, b]输出区间内素数个数。a < b, a,b属于int, b - a <= 1e5。
分析：
[a, b]区间的每个合数可以用[2, m](m = sqrt(b))中的所有数筛掉。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 100010; //最大区间长度int prime_cnt;
int prime_list[MAX_N];
bool prime[MAX_N]; //prime[i] = true:i + L是素数void SegmentPrime(int L, int R)
{int len = R - L + 1; //区间长度for(int i = 0; i < len; i++) prime[i] = true; //初始全部为素数int st = 0;if(L % 2) st++; //L是奇数for(int i = st; i < len; i += 2) { prime[i] = false; } //相当于i + L是合数，把[L, R]的偶数都筛掉int m = (int)sqrt(R + 0.5);for(int i = 3; i <= m; i += 2){ //用[3, m]之间的数筛掉[L, R]之间的合数if(i > L && prime[i - L] == false) { continue; } //i是[L, R]区间内的合数,此时[L, R]区间中中以i为基准的合数已经被筛掉了int j = (L / i) * i; //此时j是i的倍数中最接近L(小于等于L)的数if(j < L) j += i; // j >= Lif(j == i) j += i; //如果j>=L且j==i且i为素数，则相当于[L, R]中的i也为素数，所以要j += ij -= L; //把j调整为[0, len)之间int first = 1;for(; j < len; j += i) { prime[j] = false; }}if(L == 1) prime[0] = false;if(L <= 2) prime[2 - L] = true; //特别注意2的情况！prime_cnt = 0;for(int i = 0; i < len; i++){if(prime[i]) prime_list[prime_cnt++] = i + L;}
}int main()
{int T, a, b, cases = 0;scanf("%d", &T);while(T--){scanf("%d%d", &a, &b);SegmentPrime(a, b);printf("Case %d: %d\n", ++cases, prime_cnt);}return 0;
}