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之間的所有質數

如何産生質數表？ 這都是用到往前搜尋，剔除不符合條件的數，避免過多的重複計算，帶點動态規劃的味道。

#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;
}