SPOJ Problem Set 2. Prime Generator 求某区间质数题解

题目大意： 给定两个数，要求产生这两个数之间的所有质数。

两个数位m和n，其范围如下：

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.

看似简单的题目，其实也不简单，一般的质数判断方法是，看这个数n能否被2到根号n之间的数除尽，如果不能，那么就是质数，当然，这里这么写程序是会超时的。

查表方法也不行，如果先产生所有的质数表，那么内存太大了，不能保存。一般现在都使用区间剔除的方法。

目前我知道的本题最快的就是二次区间剔除的方法了：

1 先产生2到32000（32000的平方大于1E9)之间的质数，作为一个质数表(增加这个质数表也是为了加速）

2 再产生n到m之间的所有质数

如何产生质数表？ 这都是用到往前搜索，剔除不符合条件的数，避免过多的重复计算，带点动态规划的味道。

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

#include <iostream>
#include <vector>
#include <string.h>  

using namespace std;  

class PrimeNumberGenerator
{
    const static int MAX_NUM = 32000;
    int PRIMES[MAX_NUM];
    int segPrimes[100000];
public:
    PrimeNumberGenerator()
    {
        memset(PRIMES, 0, sizeof(PRIMES));
        int j = 0;
        for (int i = 2; i < MAX_NUM; i++)
        {
            if (!PRIMES[i])
            {
                PRIMES[j++] = i;
                for (int k = i*2; k < MAX_NUM; k+=i)//不是k++注意
                {//写成 k = i+1，头痛错误!!!
                    PRIMES[k] = 1;
                }
            }
        }
        PRIMES[j++] = MAX_NUM;
    }  

    //本题不需使用的函数
    bool isPrimeNum(int num)
    {
        if (2 == num) return true;
        int i = 0;
        for ( ; PRIMES[i] * PRIMES[i] <= num && num % PRIMES[i]; i++);
        return MAX_NUM != PRIMES[i] && num % PRIMES[i] != 0;
    }  

    void getSegPrimes(int a, int b)
    {
        memset(segPrimes, 0, sizeof(segPrimes));//每一次都需要memset
        for (int i = 0; PRIMES[i]*PRIMES[i] <= b; i++)//错误写成i <= b-a
        {
            int am = a/PRIMES[i];
            for (int d = am; d * PRIMES[i] <= b; d++)
            {
                if (d > 1 && d * PRIMES[i] >= a) segPrimes[d*PRIMES[i]-a] = 1;
            }//这里不能少了判断条件d>1
        }
    }  

    void judgePrimes()
    {
        int a = 0, b = 0;
        int T = 0;
        cin>>T;
        while (T--)
        {
            cin>>a>>b;
            if (a < 2) a = 2;
            getSegPrimes(a, b);
            for (int i = a ;  i <= b; i++)
            {
                if (0 == segPrimes[i-a]) cout<<i<<endl;
            }
            cout<<endl;
        }
    }
};  

int main()
{
    PrimeNumberGenerator pri;
    pri.judgePrimes();
    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索generator
， 质数
， 题目
， 两个
， 区间
范围
prime generator、spoj qtree、spoj1812、spoj 375、spoj lcs2，以便于您获取更多的相关知识。