ls学习笔记note28：线性筛选素数(埃氏筛+欧拉筛)+欧拉函数(预备填坑:扩展埃氏筛)
paperghost_ls · · 个人记录
观前提示：数论一定！一定！一定要开long long!!!
安利文章:洛谷日报:浅谈素数筛优化和欧拉系列(详细证明!)
在说欧拉函数之前，我们先来看看线性筛选素数
【题意】
素数表如下：
2、3、5、7、11、13、17…………
有n次询问，每次问第几个素数是谁？【输入格式】
第一行n(1<=n<=10000)
下来n行，每行一个整数pi，表示求第pi个素数。1<=pi<=100 0000【输出格式】
每次询问输出对应的素数。
【样例输入】
3
1
4
7【样例输出】
2
7
17我们先来看看埃氏筛选素数：
#include<cstdio>
#define ri register int
using namespace std;
int prime[150000],plen;//记录素数(prime意为素数)
bool v[2100000];//标记是否为素数，true代表是合数，但是不一定是合数就标记上，比如4。其它偶数应该是可以的
int main()
{
int n;scanf("%d",&n);
prime[1]=2;plen=1;//特例，2为素数
for(ri i=3;i<=2100000;i+=2)//因为不在可能是偶数，所以+2
{
if(!v[i])//之前没有遍历过
{
prime[++plen]=i;//加一个素数
for(int j=i*2;j<=2100000;j+=i)v[j]=true;//其倍数全部标记为合数
}
}
while(n--)
{
int x;scanf("%d",&x);
printf("%d\n",prime[x]);//直接输出
}
return 0;
}这个和线性筛选素数已经差不多了。埃氏筛选素数最大的缺点就是有一些早已标记过是合数的点会多次标记，比如120，会被3标记，被4标记，被5标记等等等等。。。要是是更大的数呢？标记多次就浪费时间了，所以我们要用线性筛选素数，避免出现筛选多次
先一个个枚举，如果没有该点被遍历过，那么就是素数。无论是素数还是合数，都要乘已有素数来遍历它的倍数，详细看代码
code：
//线性筛选素数(欧拉筛)
#include<cstdio>
#include<cstring>
#define ri register int
using namespace std;
bool v[110000000];//v[i]=true表示i为素数，false为合数
int prime[5100000],len;//prime记录素数，len为素数的个数
int main()
{
int n;scanf("%d",&n);
memset(v,true,sizeof(v));//全部假设是素数
v[1]=false;//1不是素数
for(ri i=2;i<=50000001;i++)
{
if(v[i])prime[++len]=i;//没有遍历过是素数，那么prime记录
for(ri j=1;j<=len&&i*prime[j]<=50000001;j++)//如果i*prime[j]还在范围以内
{
v[i*prime[j]]=false;//标记为合数
if(i%prime[j]==0)break;//最重要的一步，i%prime[j]==0说明这个数已经被遍历过了，无需执行后面的步骤
}
}
for(ri i=1;i<=n;i++)
{
int x;scanf("%d",&x);
printf("%d\n",prime[x]);//输出
}
return 0;
}好，接下来讲讲欧拉函数
【题意】
什么是欧拉函数phi(x)？phi(x)表示小于或等于n的正整数中与n互质的数的数目。
有n次询问，每次问phi(x)的值。【输入格式】
第一行n(1<=n<=10000)；
下来n行，每行一个整数x，表示求phi(x)。(1<=x<=2000 0000)【输出格式】
每次询问输出一行一个整数phi(x)。【样例输入】
3
10
20
100【样例输出】
4
8
40欧拉函数ϕ(n)是不超过n且和n互质的正整数的个数。欧拉函数φ(n)的作用就是转化，从而简化运算（小性质：n的所有质因子之和=eular(n) * n/2)
欧拉函数的几个性质：
1.对于质数a，φ(a)=a−1
2.对于质数a且b % a=0,φ(a b)=φ(b) a
3.若a,b,互质，φ(a b)=φ(a) φ(b)
这个和线性筛选函数密切相关，代码如下：
#include<cstdio>
#include<cstring>
#define ri register int
using namespace std;
bool v[10000005];
int phi[10000005],prime[10000005],len;
//phi就是φ
int main()
{
int n;scanf("%d",&n);
memset(v,true,sizeof(v));
phi[1]=1;v[1]=true;//1的欧拉函数值为1
for(ri i=2;i<=10000005;i++)
{
if(v[i])
{
phi[i]=i-1;//性质1
prime[++len]=i;
}
for(ri j=1;j<=len&&i*prime[j]<=10000005;j++)
{
v[i*prime[j]]=false;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];//性质2
break;
}
else phi[i*prime[j]]=phi[i]*phi[prime[j]];//性质3
}
}
for(ri i=1;i<=n;i++)
{
int x;scanf("%d",&x);
printf("%d\n",phi[x]);
}
return 0;
}但是这个方法内存占用太大，我们得换一种方法：
phi(x)=x (1-1/p1) (1-1/p2) ... (1-1/pn)
证明：
也就是说，把这个数分解质因数就可以了
我们来看一组数据：
1
100
ans=40100是要怎么分呢？我们知道，100分解质因数是这样的：
100=2*2*5*5那么，100里面含有2，5这两个因子，所以说，2，5，以及它们的倍数都不会与100互质，自然也就不算了
我们可以假设100的欧拉函数值ans就是100，然后搜到2，减去有2这个因子的数，由于100里面有50个含2因子的数，正好是100/2=50个，那么就剩下100-50=50，同时分解100，除2再除2，剩下25
然后搜到5，减去含有5这个因子的数，一共有100/5=20，但有一些和含2的重复，已经减去，所以只要在剩下的50再除以5即可，也就是再减去50/5=10个，那么现在的ans=40，除5再除5，剩下1，好了，分解完毕，ans=40
就是用这种方法来分，再比如一个数120
120=2*2*2*3*5
ans=32按上面所说的方式，搜到2，ans减去120/2=60，ans=60，分解成15
搜到3，ans减去60/3=20，ans=40，分解成5
搜到5，ans减去40/5=8，ans=32，分解成1，完毕
代码：
#include<cstdio>
#define ri register int
using namespace std;
typedef long long ll;
ll getphi(ll x)
{
ll ans=x;
for(ri i=2;i*i<=x;i++)//搜到x的开方
{
if(x%i==0)//不可能除到合数，因为在此之前已经分解完质因数了
{
ans-=ans/i;//减去i以及其倍数
while(x%i==0)x/=i;//分解质因数
}
}
if(x>1)ans-=ans/x;//因为搜到x的开方，所以如果没有除完的话就再除以一次
return ans;
}
int main()
{
int n;scanf("%d",&n);
for(ri i=1;i<=n;i++)
{
ll x;scanf("%lld",&x);
printf("%lld\n",getphi(x));
}
return 0;
}关于欧拉函数就到这里
update 2020/4/5 19:06 增加埃氏筛选素数
update 2020/7/3 13:39 找到一个好玩的东西，扩展埃氏筛，先放一篇博文，有空回来填坑~