UVa problem 11417: sample algorithm

To solve problem 11417 (GCD), it would be beneficial if one knows about the Euclidean algorithm and division algorithm. One could search up "greatest common divisor" in Google and browse through the corresponding Wikipedia article.

The algorithm to get the greatest common divisor between two numbers i and j can be best explained through an example. Consider i = 18 and j = 84, to get the GCD:

84 / 18 = 4 R 12
18 / 12 = 1 R 6
12 / 6 = 2 R 0

GCD for 18 and 84 is then 6.

Another example: i = 16 and j = 56:

56 / 16 = 3 R 8
16 / 8 = 2 R 0

GCD for 16 and 56 is then 8.

In the process illustrated above, the divisor that caused the remainder to be 0 is the greatest common divisor.

UVa problem 11417: sample code

001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005 
006   int   n
007       , g
008       , i
009       , j
010       , k
011       , i0
012       , j0
013       ;
014 
015   while (fgets(line, 100, stdin)) {
016     sscanf(line, "%d", &n);
017 
018     if (n == 0) {
019       break;
020     }
021 
022     for(i = 1, g = 0; i < n; i++) {
023       for(j = i + 1; j <= n; j++) {
024         i0 = i;
025         j0 = j;
026 
027         for (; 1; ) {
028           k = j % i;
029 
030           if (k == 0) {
031             break;
032           }
033 
034           j = i;
035           i = k;
036         }
037         g += i;
038 
039         j = j0;
040         i = i0;
041       }    
042     }
043 
044     printf("%d\n", g);
045   }
046 
047   return 0;
048 }