欧拉函数2
记得前面自己写的那个欧拉函数,自己以为应该能够应付所有的和欧拉函数有关的题了.可是这两天遇到的题让我知道.远远还不够.首先欧拉函数可以写的更快.用的是和筛素数一样的筛法.然后就是如果我需要求1-1e9的所有数的欧拉函数的话,那么,对于OJ上的题来说,内存是不够的.怎么办呢？我的做法是:求出从1-sqrt(n)的所有数的欧拉函数,然后求出1-sqrt(n)以内的所有素数.接下来,如果需要求phi(n),n
void init(int n)//n是需要求欧拉函数的最大值
{//结果存在eular数组中
int i,j
memset(eular,0,sizeof(eular));
eular[1]=1
idx=0
for(i=2i<=n;i++)
{
if(0 == eular[i])
{//i是素数
prime[idx++]=i
for(j=ij<=n;j += i)//j从i到n
{
if(0 == eular[j])
eular[j]=j
eular[j] = eular[j]/i(i-1);
}
}
}
}
int get_eular(int n)
{
int ret
int i,k
if(n<31623)//这里的31623是sqrt(n);
return eular[n];
for(i=0i<idx;i++)
{
if(0 == (n%prime[i]))
break
}
if(i==idx)//n是素数
return n-1
k = n/prime[i];
if(0 == (k%prime[i]))
ret=get_eular(k)prime[i];
else
ret=get_eular(k)*(prime[i]-1);
return ret
}
{//结果存在eular数组中
int i,j
memset(eular,0,sizeof(eular));
eular[1]=1
idx=0
for(i=2i<=n;i++)
{
if(0 == eular[i])
{//i是素数
prime[idx++]=i
for(j=ij<=n;j += i)//j从i到n
{
if(0 == eular[j])
eular[j]=j
eular[j] = eular[j]/i(i-1);
}
}
}
}
int get_eular(int n)
{
int ret
int i,k
if(n<31623)//这里的31623是sqrt(n);
return eular[n];
for(i=0i<idx;i++)
{
if(0 == (n%prime[i]))
break
}
if(i==idx)//n是素数
return n-1
k = n/prime[i];
if(0 == (k%prime[i]))
ret=get_eular(k)prime[i];
else
ret=get_eular(k)*(prime[i]-1);
return ret
}
