欧拉函数模板

 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 }