Farey Sequence

Time Limit: 1000MS		Memory Limit: 65536K

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.

There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 10⁶). There are no blank lines between cases. A line with a single 0 terminates the input.

For each test case, you should output one line, which contains N(n) ---- the number of terms in the Farey sequence Fn.

2

3

4

5

0

1

3

5

9

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define ll long long

#define esp 1e-13

const int N=1e3+,M=1e6+,inf=1e9+,mod=;

ll p[M],ji;

bool vis[M];

ll phi[M];

ll sum[M];

void get_eular(int n)

{

    ji = ;

    memset(vis, true, sizeof(vis));

    for(int i = ; i <= n; i++)

    {

        if(vis[i])

        {

            p[ji ++] = i;

            phi[i] = i - ;

        }

        for(int j = ; j < ji && i * p[j] <= n; j++)

        {

            vis[i * p[j]] = false;

            if(i % p[j] == )

            {

                phi[i * p[j]] = phi[i] * p[j];

                break;

            }

            else

            phi[i * p[j]] = phi[i] * phi[p[j]];

        }

    }

}

int main()

{

    int x,i;

    get_eular(M);

    memset(sum,,sizeof(sum));

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

    sum[i]=sum[i-]+phi[i];

    while(~scanf("%d",&x))

    {

        if(!x)break;

        printf("%lld\n",sum[x]);

    }

    return ;

}