Determine the greatest common divisor, Data Structure & Algorithms

Determine the greatest common divisor (GCD) of two integers, m & n. The algorithm for GCD might be defined as follows:

While m is greater than zero:

If n is greater than m, swap m and n.

Subtract n from m.

n is the GCD

Code in C

int gcd(int m, int n)

/* The precondition are following: m>0 & n>0. Let g = gcd(m,n). */


while( m > 0 )


if( n > m )

{ int t = m; m = n; n = t; } /* swap m & n*/

/* m >= n > 0 */

m - = n;


return n;


Posted Date: 4/4/2013 6:17:40 AM | Location : United States

Related Discussions:- Determine the greatest common divisor, Assignment Help, Ask Question on Determine the greatest common divisor, Get Answer, Expert's Help, Determine the greatest common divisor Discussions

Write discussion on Determine the greatest common divisor
Your posts are moderated
Related Questions
Q. Explain Dijkstra's algorithm for finding the shortest path in the graph given to us.  Ans: The Dijkstra's algorithm: This is a problem which is concerned with finding

1. What is an expert system and where are they needed? 2. What are the major issues involved in building an expert system?

: Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input: a b + c d +*f ­ .

Comparative Study of Linear and Binary Search Binary search is lots quicker than linear search. Some comparisons are following: NUMBER OF ARRAY ELEMENTS EXAMINED array

Define the term array. An array is a way to reference a series of memory locations using the same name. Each memory location is represented by an array element. An  array eleme

Merge sort: Merge sort is a sorting algorithm that uses the idea of split and conquers. This algorithm splits the array into two halves, sorts them separately and then merges t

what happen''s in my computer when i input any passage

* Initialise d & pi* for each vertex v within V( g ) g.d[v] := infinity  g.pi[v] := nil g.d[s] := 0; * Set S to empty * S := { 0 }  Q := V(g) * While (V-S)

It is a naturally occurring sorting method exemplified through a card player arranging the cards dealt to him. He picks up the cards like they are dealt & added them into the neede

compare and contrast the bubble sort,quick sort,merge sort and radix sort