{"id":29936,"date":"2024-05-31T15:02:46","date_gmt":"2024-05-31T09:32:46","guid":{"rendered":"https:\/\/codeforgeek.com\/?p=29936"},"modified":"2024-05-31T15:02:47","modified_gmt":"2024-05-31T09:32:47","slug":"numpy-gcd-in-python","status":"publish","type":"post","link":"https:\/\/codeforgeek.com\/numpy-gcd-in-python\/","title":{"rendered":"numpy.gcd() in Python: Finding the GCD of Arrays"},"content":{"rendered":"\n<p>The <strong>gcd function<\/strong> in <strong>NumPy<\/strong> is used to calculate the <strong>greatest common divisor<\/strong> of numbers in arrays (GCD). It is used to facilitate fractions and solve many mathematical problems. Without this function, discovering the GCD would take longer and be more<strong> error-prone<\/strong>, particularly when dealing with <strong>large datasets<\/strong>. After reading this article, you will know about this function, its algorithm, syntax, and working along with some code examples. So let\u2019s get started.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">How to Find the GCD?<\/h2>\n\n\n\n<p>We can find the GCD of any pair of numbers using a basic algorithm called the <strong>Euclidean algorithm<\/strong>. Euclidean algorithm is a method to find the largest number that can divide two other numbers without leaving a remainder.<\/p>\n\n\n\n<p>Think of two numbers, say <strong>21<\/strong> and <strong>49<\/strong>. Now, find the largest number that can divide both of them without leaving a <strong>remainder<\/strong>. This number is called the <strong>Greatest Common Divisor<\/strong> (GCD).<\/p>\n\n\n\n<p><strong>Here are the steps of how this algorithm works on these two numbers:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img decoding=\"async\" width=\"392\" height=\"286\" src=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/04\/illustration2-10.png\" alt=\"Algorithm works on two numbers\" class=\"wp-image-29959\" srcset=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/04\/illustration2-10.png 392w, https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/04\/illustration2-10-300x219.png 300w\" sizes=\"(max-width: 392px) 100vw, 392px\" \/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Divide:<\/strong> We start by dividing the bigger number by the smaller one. For 49 \u00f7 21, we get 2 with a remainder of 7.<\/li>\n\n\n\n<li><strong>Check the remainder:<\/strong> If the remainder is zero, we&#8217;re done! But since it&#8217;s 7, we move to the next step.<\/li>\n\n\n\n<li><strong>Update:<\/strong> Now, we replace the bigger number with the smaller one, and the smaller number with the remainder. So, a = 21 and b = 7.<\/li>\n\n\n\n<li><strong>Repeat:<\/strong> Divide 21 by 7. We get 3 with no remainder. So, the GCD is the last non-zero remainder, which is 7.<\/li>\n<\/ul>\n\n\n\n<p><em>Also, if you are curious about how to find remainders using NumPy in Python, check out &#8211; <a href=\"https:\/\/codeforgeek.com\/numpy-remainder-in-python\/\" data-type=\"link\" data-id=\"https:\/\/codeforgeek.com\/numpy-remainder-in-python\/\">numpy.remainder()<\/a><\/em><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Introducing numpy.gcd<\/h2>\n\n\n\n<p>It was important to understand the Euclidean algorithm before introducing the function because now that it is clear, let us understand this NumPy function.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Syntax:<\/h3>\n\n\n\n<p>The root syntax of numpy.gcd function looks like this:<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nnumpy.gcd(a,b)\n<\/pre><\/div>\n\n\n<p><strong>a<\/strong> and <strong>b<\/strong> can be either single numbers or arrays. They represent the numbers for which you want to find the GCD. The return value of this function is the greatest common divisor according to the provided input value.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Working:<\/h3>\n\n\n\n<p>The function uses the <strong>Euclidean algorithm<\/strong> with a &#8216;<strong>while<\/strong>&#8216; loop. It keeps finding the remainder when <strong>a<\/strong> is divided by <strong>b<\/strong> and updates the values of <strong>a <\/strong>and <strong>b<\/strong> until <strong>b <\/strong>becomes <strong>zero<\/strong>. When <strong>b <\/strong>reaches <strong>zero<\/strong>, <strong>a <\/strong>holds the <strong>greatest common divisor<\/strong> (GCD).<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img decoding=\"async\" width=\"410\" height=\"438\" src=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/04\/illustration-6.png\" alt=\"Flow Chart\" class=\"wp-image-29960\" srcset=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/04\/illustration-6.png 410w, https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/04\/illustration-6-281x300.png 281w\" sizes=\"(max-width: 410px) 100vw, 410px\" \/><\/figure>\n\n\n\n<p><strong>Here is the stepwise working:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Initialization<\/strong>: We begin by setting up the function and giving it two numbers or arrays, <strong>a<\/strong> and <strong>b<\/strong>.<\/li>\n\n\n\n<li><strong>Loop<\/strong>: We use a <strong>while<\/strong> loop to do the Euclidean algorithm for finding the GCD. This method keeps finding the remainder when we divide <strong>a<\/strong> by <strong>b<\/strong> until <strong>b<\/strong> reaches <strong>zero<\/strong>.<\/li>\n\n\n\n<li><strong>Update<\/strong>: Each time we go through the loop, we change the value of <strong>a<\/strong> to be what <strong>b<\/strong> was, and <strong>b<\/strong> to be the remainder when <strong>a<\/strong> is divided by <strong>b<\/strong>.<\/li>\n\n\n\n<li><strong>Result<\/strong>: When <strong>b <\/strong>becomes <strong>zero<\/strong>, the last value of <strong>a <\/strong>that isn&#8217;t zero is the <strong>GCD<\/strong>. We give back this number.<\/li>\n<\/ul>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>If <strong>a<\/strong> and <strong>b<\/strong> are single numbers, it gives the highest common factor of those two. If they are arrays, it calculates the highest common factor for each pair of numbers in the arrays.<\/p>\n<\/blockquote>\n\n\n\n<h2 class=\"wp-block-heading\">Examples of numpy.gcd in Python<\/h2>\n\n\n\n<p>Let&#8217;s gain a better understanding of numpy.gcd function with a bunch of examples.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong> First, let&#8217;s test this function with scalar values.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nimport numpy as np\n\na = int(input(&quot;Enter the first number: &quot;))\nb = int(input(&quot;Enter the second number: &quot;))\n\nprint(&quot;GCD of the given input is:&quot;, np.gcd(a,b))\n<\/pre><\/div>\n\n\n<p>This code finds the GCD of two numbers. It asks the user to enter two numbers and then prints GCD.<\/p>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img decoding=\"async\" width=\"515\" height=\"133\" src=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/output-1.png\" alt=\"Example 1 Output\" class=\"wp-image-29962\" srcset=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/output-1.png 515w, https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/output-1-300x77.png 300w\" sizes=\"(max-width: 515px) 100vw, 515px\" \/><\/figure>\n\n\n\n<p><strong>Example 2:<\/strong> Now let&#8217;s provide the array input.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nimport numpy as np\n\na_input = input(&quot;Enter the first array with separating spaces: &quot;)\narr1 = np.array(&#x5B;int(x) for x in a_input.split()])\n\nb_input = input(&quot;Enter the second array with separating spaces: &quot;)\narr2 = np.array(&#x5B;int(x) for x in b_input.split()])\n\nprint(&quot;GCD of the given input is:&quot;, np.gcd(arr1, arr2))\n<\/pre><\/div>\n\n\n<p><strong>Output:<\/strong> <\/p>\n\n\n\n<p>It will return an array containing the GCDs when comparing the elements at the same index. When comparing 24 and 12, we get 12, when comparing 13 and 26, we get 13, and so on.<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img decoding=\"async\" width=\"516\" height=\"142\" src=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/output2.png\" alt=\"Example 2 Output\" class=\"wp-image-29963\" srcset=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/output2.png 516w, https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/output2-300x83.png 300w\" sizes=\"(max-width: 516px) 100vw, 516px\" \/><\/figure>\n\n\n\n<p><strong>Example 3:<\/strong> Let&#8217;s provide huge numbers and see if it works.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nimport numpy as np\n\na = int(input(&quot;Enter the first number: &quot;))\nb = int(input(&quot;Enter the second number: &quot;))\n\nprint(&quot;GCD of the given input is:&quot;, np.gcd(a,b))\n<\/pre><\/div>\n\n\n<p><strong>Output:<\/strong> <\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img decoding=\"async\" width=\"511\" height=\"140\" src=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/output3.png\" alt=\"Example 3 Output\" class=\"wp-image-29964\" srcset=\"https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/output3.png 511w, https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/output3-300x82.png 300w\" sizes=\"(max-width: 511px) 100vw, 511px\" \/><\/figure>\n\n\n\n<p>And it works! This code proves that this function can handle huge sets of data efficiently.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>The numpy.gcd() in Python is used to calculate the greatest common divisor of numbers present at the same index in the given arrays. In this article, we learned how to find the GCD of numbers, and discussed the numpy.gcd() function in detail, and covered its syntax and parameters. Additionally, we went through some good examples for better understanding. We hope you enjoy our content.<\/p>\n\n\n\n<p><em>You may continue your learning by reading <a href=\"https:\/\/codeforgeek.com\/numpy-cumsum-python\/\">how can you calculate cumulative sum with Numpy<\/a> in Python.<\/em><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Reference<\/h2>\n\n\n\n<p><a href=\"https:\/\/numpy.org\/doc\/stable\/reference\/generated\/numpy.gcd.html\" target=\"_blank\" rel=\"noopener\">https:\/\/numpy.org\/doc\/stable\/reference\/generated\/numpy.gcd.html<\/a><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The gcd function in NumPy is used to calculate the greatest common divisor of numbers in arrays (GCD). It is used to facilitate fractions and solve many mathematical problems. Without this function, discovering the GCD would take longer and be more error-prone, particularly when dealing with large datasets. After reading this article, you will know [&hellip;]<\/p>\n","protected":false},"author":104,"featured_media":29966,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_surecart_dashboard_logo_width":"180px","_surecart_dashboard_show_logo":true,"_surecart_dashboard_navigation_orders":true,"_surecart_dashboard_navigation_invoices":true,"_surecart_dashboard_navigation_subscriptions":true,"_surecart_dashboard_navigation_downloads":true,"_surecart_dashboard_navigation_billing":true,"_surecart_dashboard_navigation_account":true,"_uag_custom_page_level_css":"","footnotes":""},"categories":[134],"tags":[],"class_list":["post-29936","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-python"],"blocksy_meta":[],"uagb_featured_image_src":{"full":["https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/Learn-how-to-calculate-greatest-common-divisor-in-Python.png",1200,600,false],"thumbnail":["https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/Learn-how-to-calculate-greatest-common-divisor-in-Python-150x150.png",150,150,true],"medium":["https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/Learn-how-to-calculate-greatest-common-divisor-in-Python-300x150.png",300,150,true],"medium_large":["https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/Learn-how-to-calculate-greatest-common-divisor-in-Python-768x384.png",768,384,true],"large":["https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/Learn-how-to-calculate-greatest-common-divisor-in-Python-1024x512.png",1024,512,true],"1536x1536":["https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/Learn-how-to-calculate-greatest-common-divisor-in-Python.png",1200,600,false],"2048x2048":["https:\/\/codeforgeek.com\/wp-content\/uploads\/2024\/05\/Learn-how-to-calculate-greatest-common-divisor-in-Python.png",1200,600,false]},"uagb_author_info":{"display_name":"Snigdha Keshariya","author_link":"https:\/\/codeforgeek.com\/author\/snigdha\/"},"uagb_comment_info":0,"uagb_excerpt":"The gcd function in NumPy is used to calculate the greatest common divisor of numbers in arrays (GCD). It is used to facilitate fractions and solve many mathematical problems. Without this function, discovering the GCD would take longer and be more error-prone, particularly when dealing with large datasets. After reading this article, you will know&hellip;","_links":{"self":[{"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/posts\/29936","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/users\/104"}],"replies":[{"embeddable":true,"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/comments?post=29936"}],"version-history":[{"count":0,"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/posts\/29936\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/media\/29966"}],"wp:attachment":[{"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/media?parent=29936"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/categories?post=29936"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeforgeek.com\/wp-json\/wp\/v2\/tags?post=29936"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}