欧拉函数与欧拉打表解决实际问题

1.欧拉函数的定义：

欧拉函数phi(x)等于不超过x且与x互素的整数的个数。

2.欧拉函数的求法：推导过程见随笔《欧拉函数与容斥原理》.

3.代码实现欧拉函数：

 1 int euler_phi(int n)
 2 {
 3     int m=(int)sqrt(n+0.5);//取一半就行，简化计算
 4     int ans=n;
 5     for(int i=2;i<=m;i++)
 6         if(n%i==0)//找素因子
 7         {
 8             ans=ans/i*(i-1);//公式的运用
 9             while(n%i==0)n/=i;//除尽
10         }
11     if(n>1)ans=ans/n*(n-1);//如果除到最后还有一个数且是大于1的素数，那么采用同样的公式再算一次
12 }

4.欧拉函数打表：（把一定范围内的整数的欧拉函数值存储起来）

 1 int phi[maxn];
 2 void phi_table(int n)
 3 {
 4     for(int i=2;i<=n;i++)phi[i]=0;//赋初值为0
 5     phi[1]=1;
 6     for(int i=2;i<=n;i++)
 7         if(!phi[i])
 8             for(int j=i;j<=n;j+=i)
 9             {
10                 if(!phi[j])phi[j]=j;//素数一般都会赋初值为自身
11                 phi[j]=phi[j]/i*(i-1);
12             }
13 }

5解决实际问题：

POJ 2478 ：

#include <iostream>
#include <stdio.h>
using namespace std;
#define LL long long
LL F[1000100];
int phi[1000100];

void phi_table(int n)
{
    for(int i=2;i<=n;i++)phi[i]=0;
    phi[1]=1;
    for(int i=2;i<=n;i++)
        if(!phi[i])
            for(int j=i;j<=n;j+=i)
            {
                if(!phi[j])phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}

int main()
{
    int n;
    F[1]=0;
    phi_table(1000000);
    for(int i=2;i<=1000000;i++) F[i] = F[i-1]+phi[i];
    while(scanf("%d",&n)&&n!=0){
        cout<<F[n]<<endl;
    }
    return 0;
}

欧拉函数打表能快速处理问题，一般不会超时。