题意：输入一个整数n(2 <= n <= 106)，输出2到n之间的欧拉函数值的和。
题目链接：http://poj.org/problem?id=2478
——>>看题目，挺短的，于是我也写了个短短的程序，先写个求一个数k的欧拉函数值的函数，然后逐个统计，结果TLE了，然后改成了与筛法类似的求2～n之间欧拉函数值的写法，结果WA，再观摩一下别人的，顿悟：最后的统计要用64位整数！
#include <cstdio>
#include <cmath>using namespace std;const int maxn = 1000000+10;
int phi[maxn];void phi_table(int n) //类似筛法的方法计算2~n的欧拉函数
{for(int i = 2; i <= n; i++) phi[i] = 0;for(int i = 2; i <= n; i++) if(!phi[i]) //固定为素数才往下for(int j = i; j <= n; j += i) //筛{if(!phi[j]) phi[j] = j;phi[j] = phi[j] / i * (i-1);}
}
int main()
{int n;phi_table(maxn); //打表while(~scanf("%d", &n)){if(!n) return 0;long long sum = 0; //这里要用64位整数！！！for(int i = 2; i <= n; i++)sum += phi[i];printf("%I64d\n", sum);}return 0;
}