萼C言語萼は素数を求めることについての考え方(普通ふるいから線形ふるいまで)

Target:正の整数nを入力して、1~nのすべての素数を出力します.
素数を求めるアルゴリズムを振り返ってみましょう.素数に関するアルゴリズムは情報学コンテストとプログラム設計コンテストでよく出題される数論知識です.今回のアルゴリズムの考え方の整理を通じて、皆さんに役に立つと思います.
1.まず一つの数が素数であるかどうかを判断する一番原始的な案:O(n＊n)
   

#include
#include
#include
bool judge(int n)
{
    int i;
    for(i=2;i

頭がいい学生はn平方をつけることによって時間の複雑さを下げることを考えるかもしれません.

#include
#include
#include
bool judge(int n)
{
    int i;
    for(i=2;i<=sqrt(n);i++)
        if(n%i==0)
        {
            return false;
            break;
        }
    return true;
}

ここで分からない学生に原理を提示してください.
因数は全部ペアで現れます.例えば、100の因数は、1と100、2と50、4と25、5と20、10と10です.すなわち、ペアの因数のうち、一つは必ず100に等しい開平方より小さく、もう一つは100に等しい開平方より大きいです.したがって、2~sqrt(n)の因数を判断すれば良いです.
2.篩法の導入
    以上のような考えがあれば、簡単に粗暴に1〜n内の個数を一度判断し、全ての素数を出力することができます.しかし、nが特に大きい場合、このようなアルゴリズムは明らかに効率が低いので、ここでフィルタの思想を提供します.n＋1のサイズのbootタイプ配列を構築し、各要素をfalseに初期化し、アルゴリズムにより素数の下付き要素値をtrueに割り当て、最後にtrue要素の下付きすべてを出力すればいいです.
    普通ふるい——エラステニふるい
長さN＋1の配列保存情報(trueは素数、falseは素数ではない)を用いて、まずすべての数が素数であると仮定し(trueに初期化)、最初の素数2から2の倍数を非素数としてマークし(falseにセットする)、Nよりも大きい.次に、2の後の次の素数3を見つけて、同じ処理を行います.最後まで、配列の中で依然としてtrueの数が素数です.

#include
#include
#define N 100
int main(void)
{
    bool number[N+1];
    int i,j;
    memset(number,true,sizeof(number));
    for(i=2;i<=sqrt(N);i++)
    {
        if(number[i]==true)//  i   
        {
            for(j=2;j*i<=N;j++)
            {
                number[i*j]=false;//  i   ， i*j    
            }
        }
    }//         false，      true
    for(i=2;i

このフィルタ法の時間複雑度はO(nloglogn)です.
アルゴリズムの改善について:

#include
#include
#define N 100
int main(void)
{
    bool number[N+1];
    int i,j;
    memset(number,true,sizeof(number));
    for(i=2;i<=sqrt(N);i++)
    {
        if(number[i]==true)//  i   
        {
            for(j=i*i;j<=N;j+=i)
            {
                number[j]=false;//     :i   ，       i*i,       i*i+2*n*i  
            }
        }
    }//         false，      true
    for(i=2;i

   
3.リニアふるい——オラエulerふるい(時間複雑度はO(n)))
上で紹介したふるいは効率がいいですが、足りないところもはっきりしています.手動でシミュレーションしてみると、多くの数が1回以上処理されていますので、大きな不必要な処理になります.以下は改善したふるいです.

#include
#include
#define N 100
int main(void)
{
    bool number[N+1];
    int prime[N+1];
    int i,j,count=0;
    memset(number,true,sizeof(number));
    for(i=2;i<=N;i++)
    {
        if(number[i])
            prime[count++]=i;
        for(j=0;j

   
    以上は筆者が整理した素数を求めるアルゴリズムです.
いくつかの考え:
1.   素数の分布範囲はどうなりますか?
n以下の素数ではなくn個の素数を求めるような問題が発生する場合があります.これは素数定理の助けが必要です.
素数の定理:素数の分布は今後ますますまばらになります.あるいは素数の密度はますます低くなります.素数の定理ははっきり言えば、数学者がある範囲の素数を推定するための公式を見つけました.大体いくつかあります.これらの公式の中で一番簡潔なのはx/ln(x)です.1,000,000以内の質数を推定するには72,382個を計算しますが、実際には78,498個あります.誤差は約8%です.推定範囲が大きいほど、偏差率が小さいのが公式の特徴です.一般的にはx/ln xである範囲の素数の個数を推定します.(誤差は15%より小さいです.)
2.    シェイプ配列とブール型配列
ブールタイプは1バイトしか占めていないので、メモリを使うには小さいです.しかし、ビットを押したいプログラムがあります.記憶されている考え方.これは上記の考え方に基づいて、空間性能を最適化したものです.C/C++出身またはアセンブリ言語で遊んだことがあります.この点を考えやすいです.Cを例にとって、bookは1バイトのメモリを占有します.1バイトは8ビットで、1ビットは0または1を表します.したがって、ビットごとに格納する方法を使うと、1バイトは8つの布になります.この境界に達するプログラム猿は、一定の長さのbyte配列を構築し、配列の各byteに8つのブール値を格納します.空間性能は、上のものに比べて8倍向上します.