Snippets Collections
def GCD(x, y):
	while(y):
		x, y = y, x % y
	return x

def generalizedGCD(nums):
	num1 = l[0]
	num2 = l[1]
	gcd = GCD(num1, num2)

	for i in range(2, len(l)):
		gcd = find_gcd(gcd, l[i])

	return gcd
// Optimised Euclidean Algorithm Code : Time Complexity : O(log(min(a,b)))

import java.io.*;
import java.util.*;

public class Main {

	static int gcd(int a, int b)
	{
		if(b==0)
			return a;

		return gcd(b, a % b);
	}

	public static void main (String[] args) {
		
		int a = 12, b = 15;

		System.out.println(gcd(a, b));

	}
}

// Euclidean Algorithm Code

  static int gcd(int a, int b)
  {
    while(a!=b)
    {
      if(a > b)
        a = a - b;
      else
        b = b - a; 
    }

    return a;
  }

// Naive Method : Time Complexity : O(min(a,b))

  static int gcd(int a, int b)
  {
    int res = Math.min(a,b);

    while(res > 0)
    {
      if(a%res == 0 && b%res == 0)
      {
        break;
      }
      res--;
    }

    return res;
  }
star

Mon Feb 21 2022 19:05:26 GMT+0000 (Coordinated Universal Time)

#python #gcd

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension