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.

Each test case has only one line, which contains a positive integer n (2 <= n <= 106).

这里依然是求欧拉函数，但是f(5)表示不仅仅是5的欧拉函数，还要包括之前所有1-4的所有欧拉函数之和。

本题的关键是由于n太大，如果直接按照3090的方法对于n,从根号n里面一个个地尝试，然后确定因数的话，则会超时。这里依然用了筛选法的思想。

#include <stdio.h>

#include <stdlib.h>

#define N 1000000

//poj2478

static char prime[N + 1];

static __int64 ans[N + 1];

int main()

{

    int i, j, n;

    prime[0] = prime[1] = 0;

    for (i=2; i<=N; i++)

        prime[i] = 1;

//原始筛选法求出所有质数

    for (i=2; i*i<=N; i++)

    {

        if (prime[i])

        {

            for (j=i*i; j<=N; j+=i)

                prime[j] = 0;

        }

    }

    for (i=1; i<=N; i++)

        ans[i] = i;

///由于所有合数最终都会被质数分解，因此对于大小为i的质数，数i,2*i,3*i....n*i一定可以被质数分解。这里不用担心某个数n先被i分解以后，不能再被质数j分解。因为如果有这种情况，说明i把N中本来可以被J整除的部分，自己整除了，即说明i,j存在公约数，显然与i,j是质数的条件矛盾。因此i一定i,2i,3i...ni质数分解。

    for (i=2; i<=N; i++)

    {

        if (prime[i])

        {

            for (j=i; j<=N; j+=i)

                ans[j] = ans[j] / i * (i - 1);//欧拉公式，先除后乘，防止越界

        }

    }

    for (i=3; i<=N; i++)

        ans[i] += ans[i - 1];

//对于i,f(i)=f(1)+f(2)+f(3)...f(i-1)。因此把前一个加到后一个即可满足要求

//    printf("ok\n");

    scanf("%d", &n);

    while (n != 0)

    {

        printf("%I64d\n", ans[n]);

        scanf("%d", &n);

    }

    return 0;

}

math2478