【素数筛法求欧拉值前n项和】POJ 2478 Farey Sequence

基德KID.1412

http://poj.org/problem?id=2478

Sample Input
2
3
4
5
0

Sample Output
1
3
5
9

求的是：sum(n) = phi(1) + phi(2) + phi(3) + ... + phi(n);

更多欧拉函数的说明：http://972169909-qq-com.iteye.com/blog/1131309

#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <iomanip>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define eps 1e-8#define PI 3.14159265358979#define inf 0x3fffffff#define L 1000005long long e[L];void Euler(){int i, j;for (i = 2; i < L; i++)e = i;for (i = 2; i < L; i++)    //筛法推L以内的数的欧拉值{if (e == i)    //一定是只有素数才可进入{e = i - 1;    //素数的欧拉值for (j = i << 1; j < L; j += i)   //筛法e[j] = e[j] - e[j]/i;    //公式}}for (i = 3; i < L; i++)    //递推求和e += e[i-1];}int main(){int n;Euler ();while (scanf ("%d", &n), n)printf ("%I64d\n", e[n]);    return 0;}