【素数筛法求欧拉值前n项和】POJ 2478 Farey Sequence
http://poj.org/problem?id=2478Sample 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;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 = e - e/i; //公式}}for (i = 3; i < L; i++) //递推求和e += e;}int main(){int n;Euler ();while (scanf ("%d", &n), n)printf ("%I64d\n", e); return 0;}
页:
[1]