[轉]素數基礎篇 之 素數的個數 -开发者知识库

[轉]素數基礎篇 之 素數的個數 -开发者知识库,第1张

   轉自:http://hi.baidu.com/vfxupdpaipbcpuq/item/0cbe522c3c9e4bcaa5275a12

1.小區間素數個數,百萬級別。

    簡述:有的時候,我們需要知道某個特定區間的素數(區間大小較小,但數可能很大)。那么數組就開不下,這時候我們仍然可以使用篩法,只是所有的下標都進行了偏移。大家理解下面這段代碼可以先用普通篩法寫,然后數組下標集體移動即可。

const int maxn = 100000;
int PrimeList[maxn];
int PrimeNum;
bool IsNotPrime[maxn]; // IsNotPrime[i] = 1表示i L這個數是素數.
void SegmentPrime(int L, int U)
{
// 求區間[L, U]中的素數.
int i, j;
int SU = sqrt(1.0 * U);
int d = U - L 1;
for (i = 0; i < d; i ) IsNotPrime[i] = 0; // 一開始全是素數.
for (i = (L % 2 != 0); i < d; i = 2) IsNotPrime[i] = 1; // 把偶數的直接去掉.
for (i = 3; i <= SU; i = 2)
{
if (i > L && IsNotPrime[i - L]) continue; // IsNotPrime[i - L] == 1說明i不是素數.
j = (L / i) * i; // j為i的倍數,且最接近L的數.
if (j < L) j = i;
if (j == i) j = i; // i為素數,j = i說明j也是素數,所以直接 i.
j = j - L;
for (; j < d; j = i) IsNotPrime[j] = 1; // 說明j不是素數(IsNotPrime[j - L] = 1).
}
if (L <= 1) IsNotPrime[1 - L] = 1;
if (L <= 2) IsNotPrime[2 - L] = 0;
PrimeNum
= 0;
for (i = 0; i < d; i ) if (!IsNotPrime[i]) PrimeList[PrimeNum ] = i L;
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复