链接：
https://vjudge.net/problem/POJ-2478
题意：
The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are
F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
You task is to calculate the number of terms in the Farey sequence Fn.
思路：
法雷级数的数的个数就是欧拉函数，欧拉函数打表前缀和即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
typedef long long LL;
const int INF = 1e9;
const int MAXN = 1e6+10;
LL phi[MAXN], prime[MAXN];
int tot, n;
void Euler()
{
phi[1] = 1;
for (LL i = 2;i < MAXN;i++)
{
if (!phi[i])
{
phi[i] = i-1;
prime[++tot] = i;
}
for (LL j = 1;j <= tot && 1LL*i*prime[j] < MAXN;j++)
{
if (i%prime[j])
phi[i*prime[j]] = phi[i]*(prime[j]-1);
else
{
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
}
}
}
int main()
{
Euler();
for (int i = 3;i < MAXN;i++)
phi[i] += phi[i-1];
while(~scanf("%d", &n) && n)
{
printf("%lld\n", phi[n]);
}
return 0;
}