Pick a depth. Each prompt opens in your AI pre-loaded with the lesson. Click a row to preview the prompt.
The least common multiple is the multiplicative dual of the gcd: where the gcd captures the largest shared factor, the lcm captures the smallest shared multiple. The reason it earns its own task is the identity , which lets you compute the lcm without ever factoring. That's the same algorithmic trick used in the rest of the course: phrase a 'multiplicative' question in terms of the gcd, then apply Euclid. The lcm itself shows up when synchronising periodic events (clock signals, polling intervals), in the Chinese remainder theorem's modulus, and in the order of products in a group — useful tools you'll meet in later modules.
The least common multiple is the smallest positive integer that is a multiple of both and . The fundamental identity ties it to the gcd: . So once you can compute gcd, lcm is one division away.
reduce(lcm, ...) to find the smallest positive integer divisible by all of . (Project Euler problem 5 — the answer is 232792560.)// main.go — run: go run main.go
package main
import "fmt"
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func lcm(a, b int) int {
if a == 0 || b == 0 {
return 0
}
if a < 0 {
a = -a
}
if b < 0 {
b = -b
}
return a / gcd(a, b) * b
}
// n-ary lcm via fold
func lcmAll(nums ...int) int {
result := nums[0]
for _, n := range nums[1:] {
result = lcm(result, n)
}
return result
}
func main() {
fmt.Println(lcm(4, 6)) // 12
fmt.Println(lcm(21, 6)) // 42
fmt.Println(lcm(1071, 462)) // 23562 = 1071*462 / 21
// n-ary lcm
fmt.Println(lcmAll(4, 6, 8, 9)) // 72
}go run main.go