判斷一個數n是否是素數，衆所周知可以用O(sqrt(n))的方法。
但是如果要求很多個數，這個方法就不太好了。（比如所有小于n的數，複雜度就是O(n1.5)。）
埃拉托斯特尼篩法，大家都聽說過。從2到n，去掉每個數的倍數，剩下來的就是質數。
不過這個方法會重複删除，比如6是2、3的倍數，會被删2次，因子越多，删的次數就越多。
改進之後的線性篩保證每個數隻被最小的質因子删，是以是O(n)的。
#include<cstdio>
#include<cstring>
#define MAXN 100005
#define MAXL 1299710
int prime[MAXN];
int check[MAXL];
int tot = 0;
memset(check, 0, sizeof(check));
for (int i = 2; i < MAXL; ++i)
{
if (!check[i])
{
prime[tot++] = i;
}
for (int j = 0; j < tot; ++j)
{
if (i * prime[j] > MAXL)
{
break;
}
check[i*prime[j]] = 1;
if (i % prime[j] == 0)
{
break;
}
}
} View Code
tot是計數用的，prime儲存質數，check是判斷是否是質數。
1.任意一個合數 A = p1p2...pn，（其中p1<=p2<=...<=pn） ，i=p2p3...pn時會删掉。
2.A隻會被p1删掉。若i是prime[j]的倍數，A不會被p[j+1]删掉，當i=A/p[j+1]時，i%p[j+1]==0，break。如果不退出，A就被p[j+1]删了。
可以看出，這個方法需要額外的prime數組。而埃氏篩不必要。
順便可以求歐拉函數
#include<cstdio>
#include<cstring>
#define MAXN 100005
#define MAXL 1299710
int prime[MAXN];
int check[MAXL];
int phi[MAXL];
int tot = 0;
phi[1] = 1;
memset(check, 0, sizeof(check));
for (int i = 2; i < MAXL; ++i)
{
if (!check[i])
{
prime[tot++] = i;
phi[i] = i - 1;
}
for (int j = 0; j < tot; ++j)
{
if (i * prime[j] > MAXL)
{
break;
}
check[i*prime[j]] = 1;
if (i % prime[j] == 0)
{
phi[i*prime[j]] = phi[i] * prime[j];
break;
}else
{
phi[i*prime[j]] = phi[i] * (prime[j]-1);
}
}
} View Code
n為質數，phi(n)=n-1
n為合數，進行質因數分解。$\large n = p_1^{k_1}\times p_2^{k_2}\times ... \times p_n^{k_n}$
$$\large \varphi(n) = n \prod\limits_{i = 1} ^ {n} \frac{p_i - 1}{p_i}$$
篩掉n=i*prime[j]時，求$\varphi(n)$，篩和求是同步的，也是O（n）。
設p1是n的最小質因子，n'=n/p1。
若n'%p1=0，即k1>1，n'含有n的所有質因子，則有
$$\large \begin{align} \varphi(n)&= n \prod\limits_{i = 1} ^ {n} \frac{p_i - 1}{p_i} \\ &= p_1 \times n' \prod\limits_{i = 1} ^ {n} \frac{p_i - 1}{p_i} \\ &= p_1 \times \varphi(n') \\ \end{align}$$
若n'%p1≠0，即k1=1，n'與p1互質，有
$$\large \begin{align} \varphi(n)&= n \prod_{i = 1} ^ {n} \frac{p_i - 1}{p_i} \\ &= p_1 \times n' \times \frac{p_1-1}{p_1} \prod\limits_{i = 2} ^ {n} \frac{p_i - 1}{p_i} \\ &= (p_1-1) \times \varphi(n') \\ \end{align}$$
（這也證明了歐拉函數是積性函數）
ref：
代碼全是抄這裡的。
歐拉函數的公式全是抄這裡的。
延伸：
隻篩奇數。
我推薦這個算法！ 易于了解。 隻算奇數部分，時空效率都還不錯！
half=SIZE/2;
int sn = (int) sqrt(SIZE);
for (i = 0; i < half; i++)
p[i] = true;// 初始化全部奇數為素數。p[0]對應3，即p[i]對應2*i+3
for (i = 0; i < sn; i++) {
if(p[i])//如果 i+i+3 是素數
{ //每次j+=k,2*(j+k)+3=(2*j+3)+2k，也就是在上一個篩的數上+2k
for(k=i+i+3, j=k*i+k+i; j < half; j+=k)
// 篩法起點是 p[i]所對應素數的平方 k^2
// k^2在 p 中的位置是 k*i+k+i
// 下标 i k*i+k+i
//對應數值 k=i+i+3 k^2
p[j]=false;
}
}
//素數都存放在 p 數組中，p[i]=true代表 i+i+2 是素數。
//舉例，3是素數，按3*3,3*5,3*7...的次序篩選，因為隻儲存奇數，是以不用删3*4，3*6.... View Code
來自：https://blog.csdn.net/dinosoft/article/details/5829550
轉載于:https://www.cnblogs.com/azureice/p/linear-sieve-for-prime-numbers.html