Question: The greatest common divisor (GCD), also known as the greatest common factor (GCF), or highest common factor (HCF), of two or more non-zero integers, is the largest positive integer that divides both the numbers without a remainder. Provide an efficient algorithm to compute GCD of two numbers.
The Euclid's algorithm is an efficient method for computing the greatest common divisor.
int gcd(int n1, int n2)
{
int temp;
if (!n1) {
return n2;
}
while (n2 != 0) {
temp = n2;
n2 = n1 % n2;
n1 = temp;
}
return n1;
}
The Euclid's algorithm is an efficient method for computing the greatest common divisor.
int gcd(int n1, int n2)
{
int temp;
if (!n1) {
return n2;
}
while (n2 != 0) {
temp = n2;
n2 = n1 % n2;
n1 = temp;
}
return n1;
}
In my opinion your explanation is bit complicated and Here is the simple and clear definition of GCF that is When there are the factors of two or more numbers and some of the factors are the common, then the largest number from those common factors is called as the Greatest Common Factor.It is Abbreviated as GCF and Also known as Highest Common Factor.
ReplyDeleteMultiplication Facts Worksheet
Well, gcd affords to be O(n), but where is n in gcd(n1, n2)?
ReplyDeleteLook at this document below (An attempt to infer the time complexity via the recurrence relation):
http://www.scribd.com/doc/164438750/Euclidian-GCD-Analysis