[SPOJ] PRIME1 – Prime Generator

http://www.chenguanghe.com/spoj-prime1-prime-generator/
http://www.spoj.com/problems/PRIME1/

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

题目大意: 给一个范围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 = 6, 4+4 = 8 4+6 =10, 这样我们可以在区间[5,10]中消除6,8,10, 这些2的倍数. 同理, 我们对每个p都做这个运算. 就可以消除所有区间的合数. 留下的就是质数. 这个方法叫Segmented Sieve of Eratosthenes.

public void solve(int testNumber, InputReader in, OutputWriter out) {

        int t = in.readInt();

        for (int i = 0; i < t; i++) {

            int m = in.readInt();

            if (m < 2) m = 2;

            int n = in.readInt();

            prime(m,n,out);

            out.printLine();

        }

    }

    public void prime(int m, int n,OutputWriter out) {

        int range = (int)Math.floor(Math.sqrt(n));

        boolean[] prime = new boolean[range];

        Arrays.fill(prime, 2, prime.length, true);

        for (int i = 2; i< range; i++)

            if (prime[i])

                for (int j = i * i; j < range; j += i)

                    prime[j] = false;

        int[] primes = new int[range + 1];

        int cnt = 0;

        for (int i = 0; i < prime.length; i++)

            if (prime[i])

                primes[cnt++] = i;

        boolean[] p = new boolean[n-m+1];

        Arrays.fill(p,true);

        for (int i = 0; i < cnt; i++) {

            if (primes[i] == 0)

                break;

            int low = m / primes[i] * primes[i];

            for (int j = low; j <= n; j+=primes[i]) {

                if (j < m)

                    continue;

                p[j-m] = false;

            }

        }

        for (int i = 0; i < cnt; i++) {

            if (m<=primes[i]&&primes[i]<=n)

                out.printLine(primes[i]);

        }

        for (int i = 0; i < n-m+1; i++) {

            if (p[i] && (i+m)!=1)

                out.printLine(i+m);

        }

    }