{"id":16128,"date":"2023-05-05T11:58:10","date_gmt":"2023-05-05T11:58:10","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=16128"},"modified":"2023-05-05T11:58:10","modified_gmt":"2023-05-05T11:58:10","slug":"program-to-find-gcd-of-two-numbers-in-cpp","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/program-to-find-gcd-of-two-numbers-in-cpp\/","title":{"rendered":"Program to Find GCD of Two Numbers in C++"},"content":{"rendered":"

\"\"<\/p>\n

The highest common number that divides two integers without leaving a remainder is known as the GCD (Greatest Common Divisor). Highest Common Factor, or HCF, is another name for GCD. Finding a GCD of two integers can assist you in building the fundamental coding and logical abilities that will advance your profession. GCD of two numbers is used to tackle many challenging problems. The fundamentals for tackling code issues are GCD of two numbers. Returning to our subject, we will examine and resolve the issue of determining the gcd of two numbers.<\/p>\n

How to Find GCD of Two Numbers in C++<\/h2>\n

Find the gcd(M,N) of the two large numbers M and N that are given.
\nThe highest possible number that divides both is GCD(M,N).
\nIt is not difficult to find the GCD of two numbers in c++ programming language. GCD of two numbers can be found by using fundamental math.<\/p>\n

Solving Approach on How To Find GCD Of Two Numbers in C++<\/h3>\n
    \n
  1. We need to store N in a string since, for the values given, we know it is less than or equal to 100 in size.<\/li>\n
  2. If we divide any number by N, we know we will always have a residue that is smaller than N.<\/li>\n
  3. We compute the remainder digit by digit to acquire the remainder by dividing a number stored String by Number. At each digit, the remainder is updated until all strings have been iterated.<\/li>\n
  4. In every iteration, we take the digit and make it greater than our current remainder by multiplying it by 10 and adding it to the digit, now we take the mod of digit by N and store it as our current remainder. After the whole string is iterated, we will get our remainder.<\/li>\n
  5. Following the division of M by N and the extraction of the remainder, both numbers fall within the long integer range, allowing us to use the long division method to obtain gcd(M,N), where M is our newly smaller number.<\/li>\n
  6. Long Division Method: We update Larger number by Smaller number and store the remainder, i.e. (Larger number% Smaller number), regularly until the smaller number entirely divides the larger number. Our gcd is the final smaller number after all steps.<\/li>\n<\/ol>\n

    Example:<\/strong>
    \nTwo numbers will be presented to us, one of which will be a string and the other a long number. Thus, we discover the remainder of string number and long number. If the given numbers are 143254 and 3, we may test the aforementioned technique by first converting 143254 to a long number, which will be 143254% 3. We take mod=0, which will store our final value, So,<\/p>\n

    \"\"<\/p>\n

    We can now use the long division approach to determine the gcd of both numbers, which is gcd(n,mod), because we know our values in integer form.<\/p>\n

    Using the long division method, we may find the gcd of two numbers, such as 25 and 135, for example.<\/p>\n

    \"\"<\/p>\n

    Dividend is our gcd(a,b) once our remainder equals 0. Let’s look at the solution for computing the gcd of two numbers in C++.<\/p>\n

    Code Implementation<\/strong><\/p>\n\t\t\t\t\t\t