UVA11417

Problem A
GCD
Input: Standard Input

Output: Standard Output

Given the value of N, you will have to find the value of G. The definition of G is given below:

Here GCD(i,j) means the greatest common divisor of integer i and integer j.

For those who have trouble understanding summation notation, the meaning of G is given in the following code:

G=0; for(i=1;i<N;i++) for(j=i+1;j<=N;j++) {     G+=GCD(i,j); } /*Here GCD() is a function that finds the greatest common divisor of the two input numbers*/

Input

The input file contains at most 100 lines of inputs. Each line contains an integer N (1<N<501). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero.  This zero should not be processed.

Output

For each line of input produce one line of output. This line contains the value of G for corresponding N.

Sample Input                              Output for Sample Input

10 100 500 0

67 13015 442011

import java.util.Scanner;

public class UVA11417 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

while (sc.hasNext()) {

int N = sc.nextInt();

if (N == 0)

break;

int G = 0;

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

for (int j = i + 1; j <= N; j++) {

G += GCD(i, j);

}

System.out.println(G);

}

sc.close();

}

private static int GCD(int i, int j) {

int temp = 0;

while (i % j != 0) {

temp = i % j;

i = j;

j = temp;

}

return j;

}

}