[SPOJ] PRIME1 – Prime Generator

原题: 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 = 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);
        }

    }