Problems 2. Prime Generator

概要

出展

https://www.spoj.pl/problems/PRIME1/

解説

指定範囲内の整数について、素数である整数を出力する。

仕様

最初に入力された数は、問題の処理数である。
問題の処理数は最大で10まで入力されることがある。
それ以降、2組の整数が、処理回数だけ入力される。
この2組の整数は、解析する範囲の、最初の数と、最後の数である。
解析する範囲は、1から1000000000の範囲内に収まる。
また、解析する範囲の整数は、100000個以内に収まる。

処理の制限時間は6秒。

（主観的な）難易度　５段階

☆☆☆☆（工夫が必要）

所感

素数を求める問題ですが、整数の範囲が大きいため、（メモリ的に）エラストテネスの篩は使えません。
そこで、「解析範囲内」で限定的にエラストテネスの篩を行うようにしなければなりません。（限定エラストテネスと呼んでおきます。）

考察

エラストテネスの篩は、《1》バッファ内に、2からnまでの整数を格納し、《2》変数iに2を代入し、《3》バッファ内にiが生きていれば、それは素数とし、《4》iにiの数を足していったものは素数ではないので、バッファを消去し、《5》iを1増やす。これを繰り返す。というものです。
今回の問題では、解析する範囲が1000000000まで来るということなので、《1》が使えません。2から1000000000までの数をバッファに取るには壮大なメモリが必要になります。
そこで、「100000個以内に収まる」という仕様に着目し、100000個のバッファだけ取るようにする必要があります。これくらいなら、メモリを確保することが可能です。
こうして、バッファには、処理を行う数値のみを格納します。

次に、処理時間的に《3》が使えません。最大100000個の数値について、iが1000000000になるまで処理を行うことになるので、とても問題の制限時間である6秒では収まりません。
このため、「解析範囲内についてのみ、その数が整数iのn倍になっているかいないか」を調べる必要があります。これが限定エラストテネスです。
まず、《2》はそのまま採用します。そして、「解析範囲内についてのみ」にするため、i×nのうち、解析範囲内での最小値を求めます。
そしてその数にnを加えていったものは、すべてiのn倍であるため、素数ではないと判断します。
こうして、バッファ内を次々と消去していきます。
また、iの最大値についてですが、エラストテネスの篩の場合は、「iは求めたい範囲の最大値」ですが、限定エラストテネスでは「√求めたい範囲の最大値」になります。
例えば、100までの整数について、これを求める場合、iは10まで良くなります。これは、x×y<=100において、xが10を超える場合、yは必ず10より小さくなるからです。xは2から始まっているので、そのようなx×yはすでに計算されていることになるからです。

こうして、限定エラストテネスによって、バッファ内を消去していき、最後まで生き残ったバッファは、i×nにならなかった数なので、素数となります。

解答例

//////////////////////////////////////////////////
//
//  Sphere Online Judge
//      2. Prime Generator
//      Problem code: PRIME1
//
//      Author  : Hau-kun
//      Date    : 2010/03/29
//
//////////////////////////////////////////////////

#include 
#include 

#define BUFFER_MAX 100001

//////////////////////////////////////////////////
//  メイン関数
//////////////////////////////////////////////////
int main(void)
{
    int nLoop = 0;                      //  処理を行う回数

    int nFirst = 0;                     //  解析する素数の範囲の始まり
    int nLast = 0;                      //  解析する素数の範囲の終わり
    int pnPrimeBuffer[BUFFER_MAX];      //  解析用バッファ
    int nBufferCounter = 0;             //  バッファ操作用
    int nNotPrime = 0;                  //  解析用、素数ではない整数

    int i = 0;
    int j = 0;


    //  入力された回数だけ処理を行う。
    scanf("%d", &nLoop);
    for(i = 0; i < nLoop; i++)
    {
        //   バッファ初期化
        for(j = 0; j < BUFFER_MAX; j++)
        {
            pnPrimeBuffer[j] = 0;
        }

        //  処理の範囲の入力
        scanf("%d %d", &nFirst, &nLast);

        //  入力された範囲の整数を、それぞれバッファに割り当てる。
        nBufferCounter = 0;
        for(j = nFirst; j <= nLast; j++)
        {
            pnPrimeBuffer[nBufferCounter++] = j;
        }

        //  バッファの各数値について、それが、ある整数 j の n 倍になっていたら素数でないと判断する。
        for(j = 2; j <= sqrt(nLast); j++)
        {
            //  解析範囲内での j × n の最小値を求める。
            nNotPrime = (nFirst / j) * j;
            while(nNotPrime < nFirst)
            {
                nNotPrime += j;
            }

            //  nNotPrime が j と等しい場合、それは素数ではないので、次の値にする。
            if(nNotPrime == j){
               nNotPrime += j;
            }

            //  nNotPrime は、j × n であるため、それに j を加えたものはすべて素数ではない。
            while(nNotPrime <= nLast)
            {
                pnPrimeBuffer[nNotPrime - nFirst] = 0;  //  nNotPrime - nFirst は、バッファ内で nNotPrime がある場所。
                nNotPrime += j;
            }
        }

        // バッファの各数値について、 0 になっていないものは素数である。
        nBufferCounter = 0;
        for(j = nFirst; j <= nLast; j++)
        {
            if(j != 1)  //  1 は素数では無いので除く。
            {
                if(pnPrimeBuffer[nBufferCounter] != 0)
                {
                    printf("%d\n", pnPrimeBuffer[nBufferCounter]);
                }
            }
            nBufferCounter++;
        }
    }

    return 0;
}

結果

TIME:0.13
MEM:1.9M

環境

Language:C(gcc 4.3.2)を指定。

Sphere Online Judgeに関する最新記事

• [2011/01/25] Sphere Online Judgeへの参戦方法 (2)
• [2010/12/27] Problems 302. Count on Cantor (0)
• [2010/10/02] Problems 2524. Conversions (1)
• [2010/03/29] Problems 2. Prime Generator (1)
• [2010/03/14] Problems 1. Life, the Universe, and Everything (1)

Sphere Online Judgeへの参戦方法はこちら