滑稽滑稽，這次我們來講講線性篩素數，讓我們先上代碼。

#include<bits/stdc++.h> using namespace std; int n,line[1000005],sushu[1000005],num=0; int main(){cin>>n;memset(line,1,sizeof(line));line[1]=0;for (int i=2; i<=n; i++){if (line[i]){num++;sushu[num]=i;}for (int l=1; l<=num && i*sushu[l]<=n; l++){line[i*sushu[l]]=0;if (i%sushu[l]==0) break;//<——藍色的語句}}return 0; }

嗯，好接下來我們來看一下這個代碼，意外的很短，但是理解起來還是有點難度的，但是其實重點就只是在那一條藍色的語句上。為什么當i是sushu[l]的倍數時就break呢？

證：

∵ i%sushu[l]==0

∴ i=k*sushu[l]

∴ i*sushu[l+1]=k*sushu[l]*sushu[l+1]=k'*sushu[l]

后面的同理，證畢。

所以這樣子的篩法就可以使得每一個合數都只被篩掉了一遍，效率快一點。

轉載于:https://www.cnblogs.com/cain-/p/7744055.html

總結

以上是生活随笔為你收集整理的模板——线性筛素数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。