1 : /* 90 algorithm van euclides (greatest common dividor) */
2 : /* author: Jan Feenstra */
3 :
4 : /* file gcd.c */
5 : /* version: 1.0 */
6 :
7 : #include <stdio.h>
8 :
9 1 : int gcd(int a, int b) {
10 4 : while ((a!=0) && (b!=0)) {
11 2 : if (a > b) {
12 1 : a = a % b;
13 : } else {
14 1 : b = b % a;
15 : }
16 : }
17 :
18 1 : if (a>b)
19 0 : return a;
20 : else
21 1 : return b;
22 : }
23 :
24 :
25 1 : int computeGCD(int a, int b) {
26 :
27 : int d;
28 :
29 :
30 1 : if (a < 0) {
31 0 : if (b < 0) {
32 0 : if (a!=b) {
33 0 : d = gcd( -a, -b);
34 : } else
35 : {
36 0 : d = 1;
37 : }
38 : } else {
39 0 : if (a!=b) {
40 0 : d = gcd( -a, b);
41 : } else
42 : {
43 0 : d = 1;
44 : }
45 : }
46 : } else {
47 1 : if (b < 0) {
48 0 : if (a!=b) {
49 0 : d = gcd( a, -b);
50 : } else
51 : {
52 0 : d = 1;
53 : }
54 : } else {
55 1 : if (a!=b) {
56 1 : d = gcd( a, b);
57 : } else
58 : {
59 0 : d = 1;
60 : }
61 : }
62 : }
63 :
64 1 : return d;
65 :
66 : }
67 :
68 : #ifndef TEST
69 : int main(int argc, char *argv[]) {
70 :
71 : int d,a,b;
72 : if (argc!=3) {
73 : fprintf(stdout,"syntax: gcd <nr1> <nr2>\n");
74 : return(-1);
75 : }
76 :
77 : sscanf(argv[1], "%d", &a);
78 : sscanf(argv[2], "%d", &b);
79 : d=computeGCD(a,b);
80 : fprintf(stdout,"gcd(%d, %d) = %d\n", a, b, d);
81 : return 1;
82 : }
83 : #endif
|