SG
← Back

Euclidean Algorithm

Efficient GCD via repeated remainder reduction.

mathgcdUpdated 2025-09-01

Loop

  • while(b!=0){ int t=a%b; a=b; b=t; }

Complexity

  • O(log min(a,b))