UVa 10820 - Send A Table

Problem Link : http://uva.onlinejudge.org/external/108/10820.html

This is an straight forward Euler Totient Function problem. Given N, you have to find the sum of Totient Function of every number from 1 to N.

Now calculating Totient Function or Phi Function on each test case would be too slow. We need to pre-calculate Totient Function of every integer upto 50000. To do this, we can modify the Sieve method and utilize the following properties -



phi(n) = n - 1, if n is prime
phi(n) = n * (p1 - 1)/p1 * (p2 - 1)/p2 * (p3 - 1)/p3 * ..., where p1, p2, p3, ... are the prime factors of n

We can initialize phi(n) to n for every number and during the Sieve, for each prime number, we adjust the Phi value of its multiples according to second formula above.

After the Sieve is finished, we assign every prime number's Phi value to n-1.

Source code follows -

#include <stdio.h>

#define MAXSIEVE 50000

char isPrime[MAXSIEVE+2];
int phi[MAXSIEVE+2];
int sum[MAXSIEVE+2];

void sieve() {
 int i,j,k=MAXSIEVE/2;
 for(i=1;i<=MAXSIEVE;i++) phi[i] = i;
 phi[1] = 0;
 for(i=2;i<=k;i++) if(!isPrime[i]) {
  for(j=i+i;j<=MAXSIEVE;j+=i) {
   isPrime[j] = 1;
   phi[j] = (phi[j] / i) * (i-1);
  }
 }
 for(i=2;i<=MAXSIEVE;i++) if(!isPrime[i]) phi[i] = i-1;
 for(i=1;i<=MAXSIEVE;i++) sum[i] = sum[i-1] + phi[i];
}

int main() {
 int n;
 sieve();
 while(scanf(" %d",&n)==1 && n) {
  printf("%d\n",2*sum[n]+1);
 }
 return 0;
}