エラトステネスのふるい

エラトステネスのふるい（Sieve of Eratosthenes）は、決められた範囲内の素数を全て求めるためのアルゴリズムです。

1〜nの範囲の素数を求めたい場合、まず適当な方法でn^1/2までの素数を求めておきます。これらの素数もふるいにかけながら求める方法もありますが、その方法は応用が利かないので、ここでは採用しません。その素数も再帰的にふるいで求めてもよいでしょう。

nまでの配列を用意して、true（素数という意味）に初期化しておきます。
最初の素数は2なので、2から順に4、6と2飛びでfalseにしていきます。3以降の素数についても同様に処理します。最後の素数まで処理して、n^1/2より大きくて、trueになっている整数が追加する素数です。

Cだとめんどうな処理が必要なので、C++/STLでコードを示します。



#include 

#include 

#include 
using namespace std;
void sieve(vector& primes, int max_p) {

    if(max_p <= 2) {

        primes.push_back(2);

    }

    else {

        int max_p_prev = int(sqrt( (double)max_p));

        sieve(primes, max_p_prev);

        vector    a(max_p + 1, true); // メモリ節約のためbool

        typedef vector::const_iterator CIT;

        for(CIT q = primes.begin(); q != primes.end(); ++q) {

            int p = *q;

            for(int k = p; k <= max_p; k += p)

                a[k] = false;

        }

        

        for(int k = max_p_prev + 1; k <= max_p; k++) {

            if(a[k])

                primes.push_back(k);

        }

    }

}
int main() {

    vector primes;

    sieve(primes, 100000000);

    cout << primes.size() << endl;

}

これとほとんど同じ処理で、素因数分解も高速に行えます。素因数分解は一般に遅いですが、まとまった整数の範囲ならこの方法が使えます。
上と同じように配列をnまでの配列を用意し、インデックスと同じ値にしておきます。また、同じ大きさの配列で、要素が空の配列のものを用意します。
そして、まず最初の素数2から4、6と2で割り切れるまで割ります。その際、2つ目の配列の対象の各要素に2を追加しておきます。指数は、あとですぐに計算できるから、メモリ節約のために記録しません。3以降も同様の処理を行います。最後に、1つ目の配列で1でない要素があれば、それは素数なので、それも2つ目の素数に追加します。
上の説明を10までで図解します。



 1  2  3  4  5  6  7  8  9 10

() () () () () () () () () ()
 1   1  3   1  5   3  7   1  9   5

() (2) () (2) () (2) () (2) () (2)
 1   1   1   1  5    1   7   1   1   5

() (2) (3) (2) () (2,3) () (2) (3) (2)
 1   1   1   1   5    1    7   1   1    5

() (2) (3) (2) (5) (2,3) (7) (2) (3) (2,5)

この方法は、素数を求めるときよりかなりメモリが必要なので、あるまとまった範囲ごとに処理を行うことが考えられます。例えば、1億までの整数の素因数分解をするには全然メモリが足りないので、100等分して100万ずつ行います。これでも十分速いです。

（追記）
リンクされていたTwitterを見ると、素因数を全部記憶しなくても、どれか一つ記憶すればいいそうです。これならメモリ使用量が少なくて済みます。ただし、それだと任意の範囲というわけにはいかないですね。