Code-Challenge: Farey sequence (II) Challenge


  In this task you would be given an integer N
  (less than 10^6), output the number of terms in the Farey
  sequence of order N.


The input N &lt; 106 is given in a single line, the inputs are terminated by EOF.

The challenge is to implement the fastest solution so that it can process a maximum of 106-1 values as fast as possible.

Input

7
10
999
9999
79000
123000


Output

19
33
303793
30393487
1897046599
4598679951


Constraints


You can use any language of your choice
Take care about your fingers, do not use more than 4096 bytes of code. 
Fastest solution, based on the running time measured for N = 106-1.
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)).