DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 834

break ;

}
}

However, this algorithm is incorrect, because n can be a divisor for m . This case must be con-
sidered. The correct algorithm is shown in Listing 22.3.

L ISTING 22.3

GCD.java
1 import java.util.Scanner;
2
3 public class GCD {
4 /** Find GCD for integers m and n */

5 public static int gcd( int m, int n) {

6 int gcd = 1 ;

7
8 if (m % n == 0 ) return n; check divisor

9
10 for ( int k = n / 2 ; k >= 1 ; k--) {
11 if (m % k == 0 && n % k == 0 ) {
12 gcd = k;
13

GCD found

break ;

14 }
15 }
16
17

return gcd;

18 }
19
20 /** Main method */
21 public static void main(String[] args) {
22 // Create a Scanner
23 Scanner input = new Scanner(System.in);
24
25 // Prompt the user to enter two integers
26 System.out.print( "Enter first integer: " );
27 int m = input.nextInt();
28 System.out.print( "Enter second integer: " );
29

input

int n = input.nextInt(); input

30
31 System.out.println( "The greatest common divisor for " + m +
32

" and " + n + " is " + gcd(m, n));

33 }
34 }

Enter first integer: 2525
Enter second integer: 125
The greatest common divisor for 2525 and 125 is 25

Enter first integer: 3
Enter second integer: 3
The greatest common divisor for 3 and 3 is 3

Assuming m n , the for loop is executed at most n/2 times, which cuts the time by half

from the previous algorithm. The time complexity of this algorithm is still O ( n ), but practi-
cally, it is much faster than the algorithm in Listing 5.9.

Ú

O ( n )