生成素数的一般方法是用“筛”，古老的 Sieve of Eratosthenes，来生成 [1,n] 之间的所有素数。这里的问题稍有变化，要求计算某个区间 [m,n] 内的素数，其中 m 和 n 都有可能很大，但是 n-m 不大。

这其实是 SPOJ 上的第二道题 (PRIME1)。

由于 m 和 n 很大，所以不能用试除法 (trial division)，而且 Sieve of Eratosthenes 也不可行。

这种情况可以用分段的筛 (segmented sieve)。也就是先用 sieve 计算出 [1,sqrt(n)] 上的素数。然后用这个素数表，在 [m,n] 上再次应用 sieve，得到所求的素数。两次的筛都不是很大，可以放在内存中，而且速度也可以接受。如果 n-m 还是很大，还可以再次分成几段来做 sieve，这是这里的做法。 (我怎么觉得后面这种情况才是 segmented sieve 呢?)

一个类似的用这种分段策略的题目是，假设一个文件里有 4 billion 个整数，数字都是普通的 int，也就是有 32 位。要求找到一个不在这个文件里的整数，限制可用内存为 10MB 。

用一般的 bitmap 肯定是不行的。可以采用分段策略，通过两次遍历完成。把 2³² 这个区间分成若干段，第一次遍历求每一个区间中数字出现的个数。然后找出一个必然存在缺失数字的区间，对这个小的区间创建 bitmap，进行第二次遍历，找到一个缺失的数字。空间复杂度满足要求，因为假设有 M 个小区间，每个区间有 N 个数，那么 M*N=2^32，第一次遍历需要 M*4B，第二次遍历需要 N*4B (假设 bitmap 都用 int 数组)。所以 M 和 N 都取为 2¹⁶ = 65536 即可。