Code Logo

GCD with Euclidean Algorithm

Published at25 Jul 2026
Created by
Number Theory Easy 0 views
Like0

Find the greatest common divisor (GCD) of two integers using the Euclidean algorithm. The GCD of two numbers is the largest positive integer that divides both numbers without a remainder.

The Euclidean algorithm repeatedly replaces the larger number with the remainder of dividing the larger by the smaller, until one number becomes 0. The GCD is the remaining non-zero number.

Example Input & Output

Example 1
Input
100,10
Output
10
Explanation

100/10

Example 2
Input
17,17
Output
17
Explanation

Same numbers

Example 3
Input
7,3
Output
1
Explanation

Prime pair

Example 4
Input
12,8
Output
4
Explanation

GCD of 12 and 8 is 4

Example 5
Input
0,5
Output
5
Explanation

GCD with 0

Algorithm Flow

Recommendation Algorithm Flow for GCD with Euclidean Algorithm
Recommendation Algorithm Flow for GCD with Euclidean Algorithm

Solution Approach

function solution(a, b) {
  while (b !== 0) { var t = b; b = a % b; a = t; }
  return a;
}

Best Answers

java
class Solution {
    public int solution(int a, int b) {
        while(b!=0){int t=b;b=a%b;a=t;}return a;
    }
}