欧拉函数模板

 1 筛选法欧拉函数
 2 int euler[3000001];
 3 void getEuler()
 4 {
 5     memset(euler,0,sizeof(euler));
 6     euler[1] = 1;
 7     for(int i = 2; i <= 3000000; i++)
 8         if(!euler[i])
 9             for(int j = i; j <= 3000000; j += i)
10             {
11                 if(!euler[j])
12                     euler[j] = j;
13                 euler[j] = euler[j]/i*(i-1);
14             }
15 }

View Code

求单个数的欧拉函数
long long eular(long long n)
{
long long ans = n;
for(int i = 2;i*i <= n;i++)
{
if(n % i == 0)
{
ans -= ans/i;
while(n % i == 0)
n /= i;
}
}
if(n > 1)ans -= ans/n;
return ans;
}