The greatest possible common divisor is an algorithm to find the greatest divisor of two given integer values.
1 | #include <iostream> |
2 | using namespace std; |
3 | |
4 | int gpcd(int, int); |
5 | int gcd(int, int); |
6 | |
7 | int main() { |
8 |     int m, n; |
9 |      |
10 |     cout << "Greatest possible common divisor" << endl; |
11 |      |
12 |     cout << "Input 1: "; |
13 |     cin >> m; |
14 |      |
15 |     cout << "Input 2: "; |
16 |     cin >> n; |
17 |     if(m <= 0 || n <= 0) |
18 |         cout << "Inputs have to greater than 0!" << endl; |
19 |     else |
20 |         cout << "The greatest possible common divisor of " << m << " and " << n << " is " << gcd(m,n) << endl; |
21 |      |
22 |     return 0; |
23 | } |
24 | |
25 | //greatest possible common devisor algorithm |
26 | int gpcd(int m, int n) { |
27 |     int r = m % n; |
28 |      |
29 |     while(r != 0) { |
30 |         m = n; |
31 |         n = r; |
32 |         r = m % n; |
33 |     } |
34 |     return n; |
35 | } |
36 | |
37 | //optimized euklid algorithm |
38 | int gcd(int a, int b) { |
39 |   if(a <= 0 || b <= 0) return -1; |
40 |   else { |
41 |       while(a != 0) { |
42 |           if(b > a) { |
43 |               int temp = a; |
44 |               a = b; |
45 |               b = temp; |
46 |           } |
47 |           a -= b; |
48 |       } |
49 |   } |
50 |   return b; |
51 | } |