← Math

GCD

Easy
Python
def gcd(a,b):
    while b: a,b=b,a%b
    return a
Java
public int gcd(int a,int b){
    while(b!=0){int t=a%b;a=b;b=t;}
    return a;
}

Key Insight

Euclid algorithm. while b vs b!=0. Simultaneous swap vs temp.

Python → Java Differences

  • while b vs b!=0
  • Simultaneous swap vs temp
  • Euclid identical
Python
def gcd(a,b):
    while b: a,b=b,a%b
    return a
Java
public int gcd(int a,int b){
    while(b!=0){int t=a%b;a=b;b=t;}
    return a;
}

Algorithm Steps

1. while b != 0
2. a, b = b, a mod b
← Previous All Math Next →