http://snippets.dzone.com/posts Sun, 27 Jul 2008 08:03:20 GMT DZone Snippets: GCD code http://snippets.dzone.com/posts/show/4583 Calculates the Greatest Common Denominator (GCD) of an array of ints using a Divide at Impera approach. <br /> <br />Time: O(lg(n)) <br />Memory: O(n) <br /> <br /><code> <br />#include <stdio.h> <br /> <br />int gcd(int a, int b) { <br /> int r = a % b; <br /> while (r) { <br /> a = b; <br /> b = r; <br /> r = a % b; <br /> } <br /> return b; <br />} <br /> <br />int gcdv(int *v, int p, int r) { <br /> if (r == p + 1) { <br /> //printf("%d,%d: %d\n", p, r, gcd(v[p], v[r])); <br /> return gcd(v[p], v[r]); <br /> } <br /> <br /> if (r == p) { <br /> //printf("%d: %d\n", r, v[r]); <br /> return v[p]; <br /> } <br /> <br /> int q = (p + r) / 2; <br /> //printf("%d,%d: %d\n", p, r, gcd(gcdv(v, p, q), gcdv(v, q + 1, r))); <br /> return gcd(gcdv(v, p, q), gcdv(v, q + 1, r)); <br />} <br /> <br />int main(int argc, char *argv[]) { <br /> int v[] = {45, 60, 125, 345, 65, 9875, 4555}; <br /> <br /> printf("GCD: %d\n", gcdv(v, 0, 6)); <br /> <br /> return 0; <br />} <br /> <br /></code> Fri, 28 Sep 2007 06:34:07 GMT http://snippets.dzone.com/posts/show/4583 scvalex (Alexandru Scvortov) http://snippets.dzone.com/posts/show/4255 This function returns the greatest common denominator (GCD) of its arguments. <br /><code> <br />int gcd(int x, int y) { <br /> int a, b; <br /> if (x<y) {a = y; b = x; } <br /> else if (x>y) {a = x; b = y; } <br /> else {return x; } <br /> do { <br /> int r = a % b; <br /> a = b; <br /> b = r; <br /> } while (b != 0); <br /> return a; <br />} <br /></code> Thu, 05 Jul 2007 03:37:26 GMT http://snippets.dzone.com/posts/show/4255 Minimiscience (Guildorn Tanaleth) http://snippets.dzone.com/posts/show/2574 // finds GCD of a and b using Euclidian algorithm <br /> <br /><code> <br />public int GCD(int a, int b) <br />{ <br /> if (b==0) return a; <br /> return GCD(b,a%b); <br />} <br /></code> Sun, 10 Sep 2006 03:28:02 GMT http://snippets.dzone.com/posts/show/2574 kanishkkunal (Kanishk Kunal) http://snippets.dzone.com/posts/show/1091 <code> <br /> ; uses GCD function <br /> lcm: func [ <br /> {Returns the least common multiple of m and n.} <br /> m [integer!] <br /> n [integer!] <br /> ][ <br /> abs either zero? n [0] [(m * n) / gcd m n] <br /> ] <br /> <br /></code> Tue, 10 Jan 2006 05:24:42 GMT http://snippets.dzone.com/posts/show/1091 gregg.irwin (Gregg Irwin) http://snippets.dzone.com/posts/show/1090 <code> <br /> gcd: func [ <br /> {Returns the greatest common denominator of m and n.} <br /> m [integer!] <br /> n [integer!] <br /> ][ <br /> ;Euclid's algorithm <br /> abs either zero? n [0] [either zero? (m // n) [n] [gcd n (m // n)]] <br /> ] <br /></code> Tue, 10 Jan 2006 05:23:33 GMT http://snippets.dzone.com/posts/show/1090 gregg.irwin (Gregg Irwin)