線形フィルタ素数...リニアだよ

前の1つのテーマはスクリーニング素数を使いましたが、それは3400以内を要求するだけで、比較的少ないので、どうでもいいです.肝心なのは100000以内を要求したら、直接要求するのはだめです.遅すぎます.
以下に、2つの自分用のテンプレートを示し、なぜ素数をすぐに計算できるのかを説明します.
コード1、これはちょっと長いですが、よく理解しています.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int prime[100000];
bool s[1000010];


void Prime()//   
{
    int i,j,k,t;
    
    for (i=2;i<=1000000;i+=2) s[i]=0;
    for (i=1;i<=1000000;i+=2) s[i]=1;
    s[1]=0; s[2]=1;
    for (i=3;i<=1010;i+=2)//    10000     ，     i%sqrt（10000）      ，      1000000    i<=1000      
    {
        if (s[i])
        {
            k=2*i;//          ，    t=3*i（   ）            ，           ，   。
            t=i+k;
            while (t<=1000000)
            {
                s[t]=0;
                t=t+k;
            }
        }
    }
    k=1; prime[1]=2;
    for (i=3;i<=1000000;i+=2)
    {
        if (s[i]==1) { k++; prime[k]=i; }
    }
    prime[0]=k; 
}

上のこれは実際にはすべての偶数を蹴って、それから、後で蹴るのは奇数だけで、さもなくばあなたは予算を繰り返します.k=2*iは偶数で、iは奇数で、3*iも奇数で、毎回t=i+kは奇数です.だから毎回除去されるのは奇数倍です.
 
このように処理すると基本的に数ごとに一度だけ素数かどうかを判断するので線形です...
 
コード2:難解な点

const int M = 3000500;
int p[400010], pNum;
bool f[M];
void Prime()
{
	int i, j;
	for(i = 2; i < M; i++) {
		if(!f[i]) { p[pNum++] = i; }
		for(j = 0; j < pNum && p[j] * i < M; j++ ) {
			f[p[j]*i] = 1;
			if(!(i%p[j]))
				break;
		}
	}
}

これは実は上のものと同じ理屈です.まずf[i]=0は素数であり,2から始まる.次に,取得した素数のi倍の数,f[p[j]*i]=1を除去する.
肝心なのは、フィルタ素数が線形であることを保証するために、次の言葉が理解しにくいことです.
なぜiはp[j]という素数を除いて飛び出すことができるのか.
簡単に証明できます
合数は、合数a=素数bを仮定しながら、1つの素数と別の数とを乗算して得ることができる×素数c×1つの数dはe=cを表す× d,b≧c,eを合数と仮定し,f=d× b a=f × c、ここでc、すなわち大きな質量数とその合数の積は、より大きな合数とそれより小さい質量数で乗算することができ、これもif(!(i%prime[j]))breakである.の意味で、これも線形ふるい法の質量数表を計算する肝心なところです
 
例を挙げます.
例えばi=9、現在素数は2 3 5 7
第2サイクルに入り、f[2*9]=1;f[3 * 9] = 1;
このとき9%3=0、飛び出すのに、なぜfをしないのか[5*9]=1;どうですか.
5*9は3*15で代用できるので、この時点で計算するとi=15までにこの数が1回繰り返されるので、ここでは重複演算を大量に回避するので、時間も節約できます.
 
ここで一言まとめると,大きな合数とこの除去可能な素数の積は,必ず小さな素数と合数よりも大きな合数の積に取って代わることができる.
わからないときは5*9=5*3*3=3*15と考えるのがこの理屈です.