45 lines
785 B
C
45 lines
785 B
C
// Laboratorio 2 - Esercizio 1
|
|
// Matteo Schiff - s295565
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
int gcd(int a, int b) {
|
|
if (b > a) { // inverti in modo che a > b
|
|
int c = a;
|
|
a = b;
|
|
b = c;
|
|
}
|
|
|
|
if (a == b)
|
|
return a;
|
|
|
|
if (b == 1)
|
|
return 1;
|
|
|
|
if (b % 2 == 0) {
|
|
if (a % 2 == 0) {
|
|
return 2*gcd(a/2,b/2);
|
|
} else {
|
|
return gcd(a, b/2);
|
|
}
|
|
} else if (a % 2 == 0) {
|
|
// il caso `a` pari, `b` dispari
|
|
// non è presente nel testo
|
|
return gcd(a/2,b);
|
|
}
|
|
|
|
return gcd((a-b)/2, b);
|
|
}
|
|
|
|
int main(int argc, char ** argv) {
|
|
int a, b;
|
|
|
|
if (argc != 3)
|
|
return 1;
|
|
|
|
a = atoi(argv[1]);
|
|
b = atoi(argv[2]);
|
|
|
|
printf("gcd: %i\n", gcd(a, b));
|
|
} |