线性素数筛+欧拉线性筛(证明)
线性素数筛
int prime[MAXN], tag[MAXN];
void Get_Prime()
{
Mem0(tag);
int cnt = 0;
for(int i = 2;i < MAXN;++i)
{
if(!tag[i])
prime[cnt++] = i;
for(int j = 0;j < cnt && i * prime[j] <= MAXN;++j)
{
tag[i * prime[j]] = 1;
if(i % prime[j] == 0)
break;
}
}
}
解释tag[i * prime[j]] = 1；
i是从小到大遍历，即所有的质数乘以大于或等于该数的数，所以所有的合数都会被筛掉且只会被筛掉一次
解释if(i%prime[j]==0) break;
相对于埃式筛，线性筛的实现是让每个数都被它的最小质因数筛去，且最小因数是质数，当跑到数字i时，我们筛掉的合数为i*prime[j] = k，这里把k分解成若干个质数的乘积，从小到大遍历所有的质数，知道k%prime[j]==0恒成立，由于prime是从小到大遍历的，所以prime[j]前面的质数一定与k互质，所以k一定被它的最小质因数筛去
欧拉线性筛
int phi[N], prime[N], vis[N], cnt;
void Euler()
{
F(i, 2, N)
{
if(!vis[i])
{
prime[cnt++] = i;
phi[i] = i - 1;
}
for(int j = 0;j < cnt && i * prime[j] < N;++j)
{
vis[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
phi[1] = 1;//定义
}
有以下公式
若x为质数，则phi[x] = x - 1
若x%prime[j] == 0,phi[x * prime[j]] = phi[x] * prime[j]
若x%prime[j] != 0,phi[x * prime[j]] = phi[x] * (prime[j] - 1)
证明二、三：
已知若i%prime[j] == 0,则prime[j]为i的质因数。下面欧拉函数的计算公式，其中p_i为x的质因数
[varphi(x)=x prod_{i=1}^{n} (1- frac{1}{p_i})
]
设x的所有质因数为
[{p_1,p_2,...,p_k}
]
证明2：若x%prime[j] == 0,有
[varphi(x* prime[j])= varphi(x) *prime[j]
]
当x%prime[j]==0，且prime[j]为质数，所以prime[j]为x的某个质因数p_j,所以由欧拉函数的计算公式得
[varphi(x*prime[j])=prime[j]*x prod_{i=1}^{k} (1- frac{1}{p_i})=prime[j]* varphi(x)
]
证明3：若x%prime[j] != 0,有
[varphi(x* prime[j])= varphi(x) *(prime[j]-1)
]
当x%prime[j]!=0时，prime[j]为i*prime[j]的质因数p_{k+1}，下面为i*prime[j]的质因数
[p_1,p_2,...,p_k,p_{k+1}(p_{k+1}=prime[j])
]
由欧拉函数的计算公式得
[varphi(x*prime[j])=prime[j]*x prod_{i=1}^{k} (1- frac{1}{p_i})*(1- frac{1}{p_{k+1}})=prime[j]* varphi(x)*(1-frac{1}{p_{k+1}})
=varphi(x)*(prime[j]-1)
]