Euclide's Algorithm to Calculate GCD

• lcam2
In summary, the program uses Euclid's algorithm to calculate the GCD of two integer arguments. The user is prompted to enter two integers and the program finds the remainder until it reaches zero. The last non-zero remainder is then outputted as the GCD.
lcam2

Homework Statement

Using Euclid's algorithm write a program with a function that determines and returns the GCD of two integer arguments.

This is what i wrote, when i print the remainder is zero, How can i get the last remaninder before the zero value?

Thanks

The Attempt at a Solution

[

#include <iostream>

using namespace std;
void remainder ( int, int); //Function Prototype

int main ()
{
int a, b;

cout << "This Program calculates the GCD of two integers \n"
<< "Please enter two integers" << endl;
cin >> a >> b;

remainder (a, b); //Calling the Function

return 0;

}

void remainder ( int a, int b) //Remainder function
{
int x, remainder;
remainder = 0;

int r;
if (a > b)
{r = b;
r %= b;
}
else
{r = a;
r %= b;
}

cout << r << endl;
}
]

You need to repeat the process until the remainder is zero and then output the other variable. For example, something like the following code should output gcd(a,b) correctly.

Code:
int r;

if (a > b)
{ r = a;
a = b;
b = r
}while (a !=0)
{ r = a;
a = b % a;
b = r
}

cout << b << endl;

What is Euclid's Algorithm to Calculate GCD?

Euclid's Algorithm is a method for finding the greatest common divisor (GCD) of two integers. It is based on the principle that the GCD of two numbers is the same as the GCD of the smaller number and the difference between the two numbers.

How does Euclid's Algorithm work?

Euclid's Algorithm works by repeatedly dividing the larger number by the smaller number, and using the remainder as the new smaller number. This process is repeated until the remainder is 0, at which point the last non-zero remainder is the GCD of the two original numbers.

What is the time complexity of Euclid's Algorithm?

The time complexity of Euclid's Algorithm is O(log n), where n is the smaller of the two input numbers. This makes it a very efficient algorithm for calculating GCDs.

Can Euclid's Algorithm be used for more than two numbers?

Yes, Euclid's Algorithm can be extended to calculate the GCD of any number of integers. This can be done by repeatedly applying the algorithm to pairs of numbers until only one number remains, which will be the GCD of all the original numbers.

What are some applications of Euclid's Algorithm?

Euclid's Algorithm has many practical applications, including cryptography, data compression, and error correction. It is also used in various mathematical and engineering fields, such as in the design of efficient algorithms and in finding the lowest common multiple of multiple numbers.

• Engineering and Comp Sci Homework Help
Replies
3
Views
811
• Engineering and Comp Sci Homework Help
Replies
2
Views
2K
• Engineering and Comp Sci Homework Help
Replies
8
Views
939
• Engineering and Comp Sci Homework Help
Replies
24
Views
2K
• Engineering and Comp Sci Homework Help
Replies
7
Views
1K
• Engineering and Comp Sci Homework Help
Replies
17
Views
1K
• Engineering and Comp Sci Homework Help
Replies
2
Views
1K
• Engineering and Comp Sci Homework Help
Replies
8
Views
1K
• Engineering and Comp Sci Homework Help
Replies
10
Views
1K
• Engineering and Comp Sci Homework Help
Replies
2
Views
1K