ふるい素数アルゴリズム(一)——線形ふるい素数アルゴリズム

時間複雑度:O(nlogn)
コードを先に上げる(コードの後ろに解析がある):

#include
using namespace std;
int n;
map Is_Prime;//           
vector Prime;//      
int main()
{
	scanf("%d",&n);//  2~n    
	for(int i=2;i<=n;i++) Is_Prime[i]=1;//         
	for(int i=2;i<=n;i++)
	{
		if(Is_Prime[i]) Prime.push_back(i);//        ，       
		for(int j=0;j

「if(!(i%Prime[j]))break」という文について説明します.
2~nの間の1つの整数iについては、2つの可能性がある.
一:それは質量数です.このときPrime[j]は必ずi(1つの素数は1と自身でしか割り切れないが、Prime[j]は1ではないので、Prime[j]はi)であり、iは保存されたばかりであり、必ず最後尾、すなわちiの後ろに他の操作可能な数がないため、ループを終了する
二:それは合数です.i=Prime[j]*x(xは2~iの整数)を得ることができ、この場合、2つの可能性がある.
1:xは質量数です.x>=Prime[j](xの場合)
2:xは合数です.xはa*bの形式(aが値を取ることができる数の中の最小質量数である)に分解することができ、i=a*b*Prime[j]である.aとPrime[j]のサイズ関係には、次の2つの可能性があります.
    ①:a
    ②:a>=Prime[j].⑪a>=Prime[j],↔b*Prime[j]<=xであれば、iはxに対して操作が既にb*Prime[j]に対して操作が行われているときに非質数と判定され、自然と再審する必要がない
証明が終わる.
 
 
 
注意:この文書で線形ふるいを習得した場合は、「いいね」をクリックしてから離れてください.もちろん、討論区でこの文の不足点を指摘することを歓迎して、作者は直ちにこの文に対して修正します
転載して住所を明記して下さい