// Week 1 – Example algorithm: greatest common divisor (Euclid)
// Run: go run ./w01/gcd
package main

import "fmt"

// Pseudocode:
//
//	Function GCD(a, b)
//	  While b ≠ 0
//	    m ← a mod b ; a ← b ; b ← m
//	  End while
//	  Return a
//	End function
func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b // parallel assignment: no helper variable needed
	}
	return a
}

// The same, printing the steps.
func gcdTrace(a, b int) int {
	fmt.Printf("%6s %6s %6s\n", "a", "b", "a mod b")
	for b != 0 {
		fmt.Printf("%6d %6d %6d\n", a, b, a%b)
		a, b = b, a%b
	}
	return a
}

func main() {
	fmt.Println("GCD(48, 18) =", gcd(48, 18))
	fmt.Println()
	r := gcdTrace(1071, 462)
	fmt.Println("GCD(1071, 462) =", r)
}