求n内与n互质的数有多少个。
欧拉函数就是为这个而生的。
如果对欧拉函数不是很了解的话，可以看看这个http://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0
我们有了上一篇埃氏筛法求素数之后，我们求这个就简单了。
具体用法就是这个函数
用最后这个公式。n可以写成
我们先来求得2到sqrt（n）的素数然后来将n化成的形式
中间如果n能整除p的话就要带入公式了。这样我们就求得最后结果了。
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
bool b[10000];
memset(b,true,sizeof(b));
for(int i=2;i<10000;i++)
{
if(b[i])
{
for(int j=i+i;j<10000;j+=i)
{
b[j]=false;
}
}
}
//上面为埃氏筛法筛素数 下面是欧拉函数的应用
int n;
while(cin>>n)
{
int nn=n;
int ans=n;
int ii=2;
while(n&&ii*ii<(nn))
{
if(b[ii]&&n%ii==0)
{
ans=ans-ans/ii;
while(n%ii==0)
{
n/=ii;
}
}
ii++;
}
cout<<ans<<endl;
}
system("pause");
}
好了！
感谢自己坚持。