UVa problem 10783: sample algorithm

For UVa problem 10783 (Odd Sum), one just has to sum up all the odd numbers between two numbers, a and b. Things can get slow if for each number between a and b, one checked if that number were odd or even, like in the following code:

for (i = a, sum = 0; i <= b; i += 1) {
__j = i mod 2;
__if (j == 1) {
____sum += i;
__}
}

To hasten the computation, we can start at an odd number in the for-loop and add 2 to the iterator index for each iteration.

First we check if a is odd or even. If it is even, we increment it to make it odd. Then we go to the for-loop:

for (j = a, sum = 0; j <= b; j += 2) {
__sum += j;
}

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.