歐拉函數有什么用

這篇文章將為大家詳細講解有關歐拉函數有什么用，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

題解：就是求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;
}

關于“歐拉函數有什么用”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。