{"id":8177,"date":"2022-09-12T07:22:45","date_gmt":"2022-09-12T01:52:45","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/"},"modified":"2022-09-12T07:22:45","modified_gmt":"2022-09-12T01:52:45","slug":"solved-greatest-common-divisor-algorithms-other-than-euclids","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/","title":{"rendered":"[Solved] Greatest common divisor algorithms OTHER than Euclid’s"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

(Note that when computing gcd(a,b)<\/code>, we can assume that a <= b<\/code>; if that were not true, we could just swap them.)<\/p>\n

The Euclidean algorithm is certainly the most efficient way to compute the gcd. But if you need two other (inefficient) ways to compute gcd(a,b)<\/code>, there are plenty:<\/p>\n

    \n
  1. \n

    Starting from a<\/code> and going down, test every number to see if it divides both a<\/code> and b<\/code>.<\/p>\n<\/li>\n

  2. \n

    Prime-factorize a<\/code> and b<\/code> (obtaining multisets of primes), and return the product of the intersection of these multisets.<\/p>\n<\/li>\n

  3. \n

    Find all divisors of a<\/code>, and test if they divide b<\/code> starting from a<\/code> and going down.<\/p>\n<\/li>\n

  4. \n

    Find lcm(a,b)<\/code> by testing which of b, 2*b, 3*b, ...<\/code> is divisible by a<\/code>, and return a*b\/(lcm(a,b))<\/code>.<\/p>\n<\/li>\n<\/ol>\n

    1 and 4 are probably easiest to implement, since they don’t involve factoring.<\/p>\n

    It’s also important to note some edge cases: gcd(0,x) = x<\/code> for all x > 0<\/code>, while gcd(0,0)<\/code> is undefined. And technically I suppose gcd(a,b) = gcd(abs(a), abs(b))<\/code> covers the case where inputs may be negative.<\/p>\n<\/p><\/div>\n

    <\/div>\n<\/div>\n

    2<\/span> <\/p><\/div>\n<\/div>\n

    [ad_2]<\/p>\n

    solved Greatest common divisor algorithms OTHER than Euclid’s <\/p>\n","protected":false},"excerpt":{"rendered":"

    [ad_1] (Note that when computing gcd(a,b), we can assume that a <= b; if that were not true, we could just swap them.) The Euclidean algorithm is certainly the most efficient way to compute the gcd. But if you need two other (inefficient) ways to compute gcd(a,b), there are plenty: Starting from a and going … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[324,2309],"class_list":["post-8177","post","type-post","status-publish","format-standard","hentry","category-solved","tag-c","tag-greatest-common-divisor"],"yoast_head":"\n[Solved] Greatest common divisor algorithms OTHER than Euclid's - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Greatest common divisor algorithms OTHER than Euclid's - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] (Note that when computing gcd(a,b), we can assume that a <= b; if that were not true, we could just swap them.) The Euclidean algorithm is certainly the most efficient way to compute the gcd. But if you need two other (inefficient) ways to compute gcd(a,b), there are plenty: Starting from a and going ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-09-12T01:52:45+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-greatest-common-divisor-algorithms-other-than-euclids\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-greatest-common-divisor-algorithms-other-than-euclids\\\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/person\\\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Greatest common divisor algorithms OTHER than Euclid’s\",\"datePublished\":\"2022-09-12T01:52:45+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-greatest-common-divisor-algorithms-other-than-euclids\\\/\"},\"wordCount\":157,\"publisher\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#organization\"},\"keywords\":[\"c++\",\"greatest-common-divisor\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-greatest-common-divisor-algorithms-other-than-euclids\\\/\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-greatest-common-divisor-algorithms-other-than-euclids\\\/\",\"name\":\"[Solved] Greatest common divisor algorithms OTHER than Euclid's - JassWeb\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#website\"},\"datePublished\":\"2022-09-12T01:52:45+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-greatest-common-divisor-algorithms-other-than-euclids\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-greatest-common-divisor-algorithms-other-than-euclids\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-greatest-common-divisor-algorithms-other-than-euclids\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Greatest common divisor algorithms OTHER than Euclid’s\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#website\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/logo\\\/image\\\/\",\"url\":\"https:\\\/\\\/jassweb.com\\\/wp-content\\\/uploads\\\/2021\\\/02\\\/jass-website-logo-1.png\",\"contentUrl\":\"https:\\\/\\\/jassweb.com\\\/wp-content\\\/uploads\\\/2021\\\/02\\\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/logo\\\/image\\\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/person\\\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/wp-content\\\/litespeed\\\/avatar\\\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/wp-content\\\/litespeed\\\/avatar\\\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400\",\"contentUrl\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/wp-content\\\/litespeed\\\/avatar\\\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\\\/\\\/jassweb.com\"],\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/author\\\/jaspritsinghghumangmail-com\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Greatest common divisor algorithms OTHER than Euclid's - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Greatest common divisor algorithms OTHER than Euclid's - JassWeb","og_description":"[ad_1] (Note that when computing gcd(a,b), we can assume that a <= b; if that were not true, we could just swap them.) The Euclidean algorithm is certainly the most efficient way to compute the gcd. But if you need two other (inefficient) ways to compute gcd(a,b), there are plenty: Starting from a and going ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/","og_site_name":"JassWeb","article_published_time":"2022-09-12T01:52:45+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Greatest common divisor algorithms OTHER than Euclid’s","datePublished":"2022-09-12T01:52:45+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/"},"wordCount":157,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["c++","greatest-common-divisor"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/","url":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/","name":"[Solved] Greatest common divisor algorithms OTHER than Euclid's - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-09-12T01:52:45+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-greatest-common-divisor-algorithms-other-than-euclids\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Greatest common divisor algorithms OTHER than Euclid’s"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/8177","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=8177"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/8177\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=8177"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=8177"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=8177"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}