浅談ふるい法

最近1つの問題をして、107内のオーラの関数を求めるので、私はオーラのふるい法を使ってオーラの関数を求めることを使って、しかし後で各種の水の法が湧き出てくることを発見して、私も酔っていました.そこでふるい方についてお話ししたいと思います.ふるい法は、その名の通り、フィルタリングの方法であり、質量数をフィルタリングしたり、素数に関連する関数を計算したりすることができます.

エラトスターニふるい

これを話す前に、エラトスターニという人についてお話しします.彼は古代ギリシャ人で、紀元前274～194年ごろにこのアルゴリズムを発明しました.本当に**ですね.具体的には、ふるい値の範囲n√を与え、n√以内の素数p 1,p 2,p 3,...,pk .まず2でふるいにかけて、すぐに2を残して、2の倍数を取り除きます;次の素数、つまり3ふるいで、3を残して、3の倍数を取り除きます.次に次の素数5ふるいで、5を残して、5の倍数を取り除きます.繰り返していく…….ギリシャ人はワックスを塗った板に数を書いているので、1つの数を引くたびに、上に小さな点を書いて、質量数を求める作業が終わった後、この多くの小さな点はふるいのようなものなので、エラトスターニの方法を「エラトスターニふるい法」と呼び、「ふるい法」と略称します.詳細は以下を参照してください.
http://baike.baidu.com/view/82625.htm

せんけいふるいほう

上記のアルゴリズムでは,同じ数が複数の異なる素数でふるい落とされる可能性があり,1つの数を1つの素数だけふるい落とすことができるかどうかを見出した.1つの数は、その最小(または最大)の質量係数によってのみふるい落とされることを規定することができる.では,このふるい法の時間は線形であり,上のアルゴリズムの最適化に相当する.どのように実現しますか?コードを見てください:

fo(i,2,N){
        if (!check[i]){
            check[i]=1;
            pri[++k]=i;
        }
        fo(j,1,k){
            if (i*pri[j]>N)break;
            f[i*pri[j]]=1;
            if (i%pri[j]==0)break;
        }
    }

他のふるいの応用については、自分で考えてみましょう.