{"id":1153,"date":"2020-06-11T10:24:43","date_gmt":"2020-06-11T10:24:43","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1153"},"modified":"2023-07-21T07:07:47","modified_gmt":"2023-07-21T07:07:47","slug":"gcd-of-two-very-large-numbers","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/gcd-of-two-very-large-numbers\/","title":{"rendered":"How to Find GCD of two very large numbers?"},"content":{"rendered":"

\"\"<\/p>\n

In this article, we will delve deep into the topic of finding the greatest common divisor, GCD of two numbers. Understanding how to find the GCD of two numbers not only improves your fundamental logical and coding skills but also enhances your career prospects. Regular practice with coding questions, such as determining the GCD of two numbers, is an excellent habit that prepares you for technical interviews with various organizations. Additionally, the GCD is a key concept used to solve many complex problems. Whether you are just starting out in coding or are already on a coding career path, grasping the basics of finding the GCD of two numbers is essential. Let’s now proceed to explore and solve the problem of finding the GCD of two numbers.<\/p>\n

How to Find GCD of Two Numbers:<\/h2>\n

For given two large numbers M and N, find their gcd(M,N).
\nGCD(M,N) is the largest number possible which divides both.
\nFinding a GCD of two numbers is not a complicated task. From basic mathematics you can solve how to find GCD of two numbers.<\/p>\n

<\/a>
\nTest Case:<\/strong><\/p>\n

Input:<\/strong> 15 130
\nOutput:<\/strong> 5<\/p>\n

Explanation:<\/strong>
\n5 divides 15 and 130 both completely and there exists no number greater than 5 which divides both of them completely.<\/p>\n

Solving Approach How To Find GCD Of Two Numbers :<\/h2>\n
    \n
  1. For provided numbers, we know N is of size less than or equal to 100, so we would need to store this number in a string.<\/li>\n
  2. We know we get the remainder less than N always if we divide any number by N.<\/li>\n
  3. To get the remainder by dividing a number stored String by Number, we calculate the remainder digit by digit. We update the remainder at every digit until all strings are iterated.<\/li>\n
  4. In each 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 get our remainder.<\/li>\n
  5. After we divide M by N and extract it\u2019s remainder, now both of them are in the Long Integer range, and we can carry with us our Long Division Method for getting gcd(M,N) where M is our new smaller number.<\/li>\n
  6. Long Division Method: We repeatedly store remainder i.e (Larger number % Smaller number) and update Larger number by Smaller number until smaller number completely divides the larger number. Last Smaller Number after all steps, is our gcd.
    \nExample:<\/strong><\/li>\n<\/ol>\n

    We\u2019ll be given two numbers out of which one is a string and one is a long number. Hence we find the remainder of string number and long number.
    \nWe can dry run the above mentioned technique,let\u2019s say given numbers are 143254 and 3, so first we convert 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

    As we have got our values in integer form, we can now use the long division method, to find out the gcd of both numbers that is gcd(n,mod).
    \nLet\u2019s take 25 and 135 for example, we find gcd of both using the Long Division Method.<\/p>\n

    \"\"<\/p>\n

    As soon as our remainder becomes 0, dividend is our gcd(a,b). Let\u2019s see all the solutions for finding gcd of two numbers in (c, java, Python).<\/p>\n

    Solutions:<\/strong>
    \n\t\t\t\t\t\t