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

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 1000005
long long e[L];

void Euler()
{
	int i, j;
	for (i = 2; i < L; i++)
		e[i] = i;
	for (i = 2; i < L; i++)    //筛法推L以内的数的欧拉值
	{
		if (e[i] == i)    //一定是只有素数才可进入
		{
			e[i] = i - 1;    //素数的欧拉值
			for (j = i << 1; j < L; j += i)   //筛法
				e[j] = e[j] - e[j]/i;    //公式
		}
	}
	for (i = 3; i < L; i++)    //递推求和
		e[i] += e[i-1];
}

int main()
{
	int n;
	Euler ();
	while (scanf ("%d", &n), n)
		printf ("%I64d\n", e[n]);
    return 0;
}

评论

2 楼 基德KID.1412 2011-08-03  

sgeteternal 写道

得吃啦~

爽

1 楼 sgeteternal 2011-08-03  

得吃啦~