欧拉函数有什么用

这篇文章将为大家详细讲解有关欧拉函数有什么用，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

题解：就是求n以内 所有互素的数 的组合数！ 即n以内所有整数的欧拉函数之和！

欧拉函数知识点 可以参考白书。

//	2478	Accepted	4084K	235MS	C++	620B	
//	2478	Accepted	8000K	282MS	C++	735B	
#include <iostream>//详细可以参见 白书！
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000010
int phi[N];
void Eula()
{
    int i,j;
    memset(phi,0,sizeof(phi));//筛法 求出N以内的所有 n以内的互素数！
    for(i=2;i<=N;i++)//素数从2开始
    {
        if(!phi[i])
        {
            for(j=i;j<=N;j+=i)
            {
                if(!phi[j]) phi[j]=j;//赋给该数 素因子分解后 它的最小素因子！
                phi[j]=phi[j]/i*(i-1);//后面每一个素因子可以组成的数 都用公式刷新下该数的 欧拉数！
            }
        }
    }
    //for(i=2;i<=N;i++)phi[i]+=phi[i-1]; 第二种方法可以把所有答案打好表！
}
int main()
{
    Eula();
    int n,i;
    __int64 sum;
    while(scanf("%d",&n),n)
    {
        sum=0;
        for(i=2;i<=n;i++)
            sum+=phi[i];
        printf("%I64d\n",sum);
    }
    return 0;
}

上面是打表的方法--适用于多数据 而数据小；

以下为求单个 数的欧拉函数--适用于大数据 小规模;

#include<stdio.h>
long long phi(long long a)
{
long long temp=a;
for(long long i=2;i*i<=a;i++)
if(a%i==0)
{
while(!(a%i))a/=i;  //该数有此素因子，先除完.
temp=temp/i*(i-1);  //利用公式 n/(1-1/p);
}
if(a!=1)  //最后a不是1 就是一个素数.
temp=temp/a*(a-1);//再利用公式除一下就ok!
return temp;
} 
int main() 
{
long long a,b,c;
while(scanf("%lld",&a)!=EOF)
printf("%lld\n",phi(a));
return 0;
}

关于“欧拉函数有什么用”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。