算法提高 欧拉函数
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法提高 欧拉函数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1477字，纯文字阅读大概需要3分钟。
内容图文
说明
2016.4.5 已更新试题，请重新提交自己的程序。
问题描述
给定一个大于1，不超过2000000的正整数n，输出欧拉函数，phi(n)的值。
如果你并不了解欧拉函数，那么请参阅提示。
输入格式
在给定的输入文件中进行读入：
一行一个正整数n。
输出格式
将输出信息输出到指定的文件中:
一行一个整数表示phi(n)。
样例输入
17
样例输出
16
提示
欧拉函数phi(n)是数论中非常重要的一个函数，其表示1到n-1之间，与n互质的数的个数。显然的，我们可以通过定义直接计算phi(n)。
当然，phi(n)还有这么一种计算方法。
首先我们对n进行质因数分解，不妨设n=p1^a1 * p2^a2 * ... * pk^ak （这里a^b表示a的b次幂，p1到pk为k个互不相同的质数，a1到ak均为正整数），那么
phi(n)=n(1-(1/p1))(1-(1/p2))....(1-(1/pk))
稍稍化简一下就是
phi(n)=n(p1-1)(p2-1)...(pk-1)/(p1*p2*...*pk)
计算的时候小心中间计算结果超过int类型上界，可通过调整公式各项的计算顺序避免(比如先做除法)!
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int Maxn=2000000;
int phi[Maxn];
void Euler1()
{
for(int i=1; i<Maxn; i++)
phi[i]=i;
for(int i=2; i<Maxn; i++)
if(i==phi[i])//prime
for(int j=i; j<Maxn; j+=i)
phi[j]=(phi[j]/i*(i-1));
}
//定义
int Euler2(int n)
{
int m=(int)sqrt(n+0.5);
int ans=n;
for(int i=2; i<=m; i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0)
n/=i;
}
}
if(n>1)
ans=ans/n*(n-1);
return ans;
}
//类似于筛选法
void Euler3(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()
{
Euler3(Maxn);
int n;
cin >> n;
cout<< phi[n] << endl;
return 0;
}
内容总结
以上是互联网集市为您收集整理的算法提高 欧拉函数全部内容，希望文章能够帮你解决算法提高 欧拉函数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。