常用的篩素數的算有兩種： 1). Eratosthenes篩法：把[1,N]素數p的倍數篩出去，剩余的就是素數。 [cpp] int prime[N], np; bool vis[N]; void get_prime() { np = 0; memset(vis, 0, sizeof(vis)); for(int i = 2; i < N; ++i) { if (!vis[i]) { prime[np++] = i; for(int j = i+i; j < N; j +=i) vis[j] = 1; } } } 算法復雜度O(N*log log N) 2). 線線篩法：Eratosthenes篩法會有很多重復的篩選，此算法是對Eratosthenes篩法的改進. 線性篩素數的基本思想是：每個合數只被篩一次，將被其最大因數篩掉。 假設我們依據flag數組從小到大判斷每個數是否是素數，如果當前該數還未被篩掉，那麼就是素數，因為在比它小的數中沒有發現因數，將素數加入素數表中。對每一個數i（不論素數或合數），用它篩掉flag數組中以它為最大因數的數。因為每個數只去篩以它為最大因數的數，所以每個合數只會被一個數篩，就是它的最大因數，以此達到線性的復雜度。www.2cto.com 假設當前的數是i。以i為最大因數的數是哪些呢？這些數必然是i乘上一個比它小的素數（如果該數是i乘上一個比它大的素數，顯然i不會是該數的最大因數；如果是i乘上一個合數x = p1*p2*...*pk （pi為素數），顯然通過將x的一些素因數與i相乘會得到比i大的因數）。 假設i可以表示為素數乘積：i = p1*p2*...*pn，x是一個比i小的素數（x顯然已經被篩出來了，在我們的素數表中），其中i最小的素因數是p1。i只有與當前素數表中p<=p1的素數相乘，得到的數y才以i為最大因數。反證：如果i乘上pm得到y = i*pm，且pm>p1，那麼y有因數y/p1 > i = y/pm。 所以對每一個數i，乘上素數表中不大於i的最小素因數p1的素數，將得到的數從flag數組中篩去，我們就可以在線性的時間復雜度下得到一個素數表。 [cpp] int prime[N], np; bool vis[N]; void get_prime2() { np = 0; memset(vis, 0, sizeof(vis)); for (int i = 2; i < N; ++i) { if (!vis[i]) prime[np++]=i; for (int j = 0,t ; j < np && (t = prime[j]*i) < N; ++j) { vis[t] = 1; if(i % prime[j] == 0) break; } } } 在該算法中，每個合數都只被最小的素數篩去，算法復雜度O(N)
