GCD: Divide Et Impera

Calculates the Greatest Common Denominator (GCD) of an array of ints using a Divide at Impera approach.

Time: O(lg(n))
Memory: O(n)


#include 

int gcd(int a, int b) {
	int r = a % b;
	while (r) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int gcdv(int *v, int p, int r) {
	if (r == p + 1) {
		//printf("%d,%d: %d\n", p, r, gcd(v[p], v[r]));
		return gcd(v[p], v[r]);
	}
	
	if (r == p) {
		//printf("%d: %d\n", r, v[r]);
		return v[p];
	}
	
	int q = (p + r) / 2;
	//printf("%d,%d: %d\n", p, r, gcd(gcdv(v, p, q), gcdv(v, q + 1, r)));
	return gcd(gcdv(v, p, q), gcdv(v, q + 1, r));
}

int main(int argc, char *argv[]) {
	int v[] = {45, 60, 125, 345, 65, 9875, 4555};
	
	printf("GCD: %d\n", gcdv(v, 0, 6));
	
	return 0;
}