? ? ? ? ? ? ? ?昨天有個SB給我講了一個線性篩選素數法O(n)的復雜度，感覺很神奇，自己看了看，

確實牛b的樣子。其實它不像一般的篩選素數法會重復操作標記非素數，此方法不會重復

之行操作，遍歷只需一次就行。

void get_prime() {int num = 0 ;memset(vis,false,sizeof(vis));for(int i = 2 ; i < n ; i ++){if(!vis[i]) prime[num++] = i ;for(int j = 0; j<num && i*prime[j]<n ; j ++){vis[i*prime[j]] = true ;if(i % prime[j] == 0) break ;}} } /*可以用均攤分析的方法來分析算法的復雜度,由于每 個合數都唯一的被它的最小素因子篩一次，而每個合 數的最小素因子都是唯一的，總復雜度是O(n)*/
一般 篩選素數法：

void get_prime() {int num = 0 ;memset(vis,false,sizeof(vis));for(int i = 2 ; i < n ; i ++){if(!vis[i]) {prime[num++] = i ;for(int j = 2*i ; j < n ; j += i){vis[j] = true ;}}} }

總結

以上是生活随笔為你收集整理的线性筛选素数法（O(n)复杂度）的全部內容，希望文章能夠幫你解決所遇到的問題。

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