POJ 2478 欧拉函数
题目
这题的实际就是求欧拉函数,也就是给你一个n,然后求从2-n的所有数的欧拉函数的和,至于不知道欧拉函数的还请google之.下面给出两个求欧拉函数的模板,一个是求从1-n的所有数的欧拉函数,一个是求单个数的欧拉函数.这两个函数都是由phi(n)=n(p1-1)(p2-1)……(pn-1)/(p1p2……*pn)这个式子来的.
第一个求所有数的欧拉函数
void eular()
{
int i,j
memset(p,1,sizeof(p));
for(i=0i<1000001;i++)
e[i]=i//初始化
for(i=2i<1000001;i++)
{
if(1==p[i])
{
e[i]–//如果是素数 那么等于n-1
for(j=2ij<1000001;j+=i)
{
p[j]=0//这里就是那个公式的应用,这里的P[j]数组是表示这个数是否是素数
e[j]=(i-1);
e[j]/=i
}
}
}
}
{
int i,j
memset(p,1,sizeof(p));
for(i=0i<1000001;i++)
e[i]=i//初始化
for(i=2i<1000001;i++)
{
if(1==p[i])
{
e[i]–//如果是素数 那么等于n-1
for(j=2ij<1000001;j+=i)
{
p[j]=0//这里就是那个公式的应用,这里的P[j]数组是表示这个数是否是素数
e[j]=(i-1);
e[j]/=i
}
}
}
}
第二个,求单个数的欧拉函数:
int eular(int n)
{
int ret=1,i
for(i=2ii<=n;i++)
{
if(n%i==0)
{
n/=i
ret=i-1
while(0==n%i)
{//这里还是那个公式的应用
n/=i
ret=i
}
}
}
if(n>1)//如果剩下的n是素数
ret=n-1
return ret
}
{
int ret=1,i
for(i=2ii<=n;i++)
{
if(n%i==0)
{
n/=i
ret=i-1
while(0==n%i)
{//这里还是那个公式的应用
n/=i
ret=i
}
}
}
if(n>1)//如果剩下的n是素数
ret=n-1
return ret
}
