原题: http://www.spoj.com/problems/PRIME1/ 题目大意: 给一个范围1 <= m <= n <= 1000000000, n-m<=100000, 找这个范围内的所有质数. 分析: spoj真是卡时间也卡空间. 做了起码五六次, 不是tle就是heap爆了. 观察了一下, 发现取值范围实在太大了, 1*10^9. 后来怀疑是不是用aks test, 试了, 还是不行. 发现问题是在方法上. 首先不能求1~n的所有质数, 然后打印出大于等于m的, 这样太慢, 其次Sieve of Eratosthenes(SoE)求的是[2,n]的. 我们需要使用的是[m,n]的.这里需要观察一下,对于每个[2,sqrt(n)]的质数p, 都有以下特点: 对于m,我们可以找到一个lower bound, 这个bound是m前边最大的能被p整除的数.比如m=5,p=2, 那么5/2 = 2(取整), 2*2 =4, 那么4就是我们要找的lower bound. 这个bound有一个特性, 就是我们用过lower bound + k*p 就可以知道p在[m,n]中出现的位置. 比如刚才的例子, m=5, n=10, 那么lower bound = 4, 4+2 […]