数学：欧拉函数

一个例题是POJ2478，给定一个数n，求在[1,n]这个范围内两两互质的数的个数

对于这个范围内的每一个数，我们只要找到不超过这个数且与这个数互质的数的个数就可以了

其实就是求欧拉函数

一个一个求的方法在欧拉定理部分有介绍，这里我们是要快速求这个欧拉函数

我在这里整理了两份，一份是利用性质求的，一份是用筛法筛的

先看看有啥性质：

phi(p^k)=(p-1)*p^(k-1)

phi(a*b)=phi(a)*phi(b)（a,b互质）

phi(p)=p-1（p为质数）

很神奇，和质数打交道

那么第一种方法可以顺便把质数表打出来？

第二种就是纯筛了，事实证明第一种方法快一丢丢

 1 #include<cstdio>
 2 const int maxn=1000005;
 3 int tot,n;
 4 bool mark[maxn];
 5 int phi[maxn],pri[maxn];
 6 long long ans;
 7 void getphi()
 8 {
 9     phi[1]=1;
10     for(int i=2;i<=1000000;i++)
11     {
12         if(!mark[i]) {pri[++tot]=i;phi[i]=i-1;}  //如果是质数 
13         for(int j=1;j<=tot;j++)
14         {
15             int x=pri[j];
16             if(i*x>1000000) break;
17             mark[i*x]=1;
18             if(i%x==0) {phi[i*x]=phi[i]*x;break;}
19             else phi[i*x]=phi[i]*phi[x]; 
20         } 
21     }
22 }
23 void getphi2()
24 {
25     for(int i=1;i<=1000000;i++) phi[i]=i;
26     for(int i=2;i<=1000000;i++)
27     {
28         if(phi[i]==i)
29             for(int j=i;j<=1000000;j+=i)
30                 phi[j]=phi[j]/i*(i-1);
31     }
32 }
33 int main()
34 {
35     getphi2();
36     while(scanf("%d",&n))
37     {
38         if(n==0) break;
39         ans=0;
40         for(int i=2;i<=n;i++) ans+=phi[i];
41         printf("%lld
",ans);
42     }
43     return 0;
44 }