Code-Challenge: Farey sequence (II)
C - 0.1 Secs on Ideone

http://www.ideone.com/E3S2t

Explanation included in code.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;

long long A[1000001]={0};
int main()
{ 
    int isprime[1001],d,n,k,i,e,p; 

    for (n=2;n&lt;1001;n++)
        isprime[n]=1;

    //Sieve of Eratosthenes for Prime
    //Storing the smallest prime which divides n.
    //If A[n]=0 it means it is prime number.
    for(d=2;d&lt;1001;d++)
    {
        if(isprime[d])
        {
            for (n=d*d;n&lt;1001;n+=d)
            {
                isprime[n]=0;
                A[n]=d;
            }
            for (;n&lt;=1000000;n+=d)
                A[n]=d;
        }
    }

    //Uses multiplicative property of
    //Euler Totient Function
    //Phi(n)=Phi(p1^k1)*Phi(p2^k2)...*Phi(pr^kr)
    //and Phi(pi^ki)=(pi-1)*(pi^(ki-1))
    A[1]=1;
    for(n=2;n&lt;=1000000;n++)
    {
        if (A[n]==0)
           A[n]=n-1;
        else
        {
           p=A[n],k=n/p,e=1;
           while (k%p==0)
                 k/=p,e*=p;
           A[n]=A[k]*e*(p-1);
        }
    }
    //Number of terms in Farey Series
    //|F(n)| = 1 + Sigma(i,1,n,phi(i))
    A[1]=2;
    for(n=2;n&lt;=1000000;n++)
        A[n]+=A[n-1];


    while (~scanf("%d",&amp;i))
        printf("%lld\n",A[i]);
    return 0;
}


A little more explanation:


  For all numbers we get a prime factor
  of it from the sieve(or 0 if it is a
  prime). Next we use the fact that ETF
  is multiplicative. That is if m and n
  are coprime then
  phi(m*n)=phi(m)*phi(n). Here we take
  out the multiple of prime factor out
  and hence the left part and the
  multiple part are co-prime. We already
  have the ETF for the left part since
  it is either smaller then current
  value or equal to 1. We only need to
  calculate the ETF for the multiple
  which we calculate using the formula
  phi(pi^ki)=(pi-1)*(pi^(ki-1)).