geom/primes/ints.go

package primes

import "opslag.de/schobers/geom/ints"

// GreatestCommonDivisor returns the greatest common divisor of a and b.
func GreatestCommonDivisor(a, b int64) int64 { return GCD(a, b) }

// GCD returns the greatest common divisor of a and b.
func GCD(a, b int64) int64 {
	factors := Factorize(a)
	var i int
	var gcd int64 = 1
	for _, f := range Factorize(b) {
		for ; i < len(factors) && factors[i].Prime < f.Prime; i++ {
		}
		if i < len(factors) && factors[i].Prime == f.Prime {
			var exponent = ints.Min(f.Exponent, factors[i].Exponent)
			gcd *= ints.Pow64(f.Prime, int64(exponent))
			i++
		}
	}
	return gcd
}

// LeastCommonMultiple returns the least common multiple of a and b.
func LeastCommonMultiple(a, b int64) int64 { return LCM(a, b) }

// LCM returns the least common multiple of a and b.
func LCM(a, b int64) int64 {
	factors := Factorize(a)
	var i int
	var lcm int64 = 1
	for _, f := range Factorize(b) {
		for i < len(factors) {
			var p = factors[i].Prime
			if p < f.Prime {
				lcm *= p
				i++
			} else {
				break
			}
		}
		var exponent = f.Exponent
		if i < len(factors) && factors[i].Prime == f.Prime {
			exponent = ints.Max(exponent, factors[i].Exponent)
			i++
		}
		lcm *= ints.Pow64(f.Prime, int64(exponent))
	}
	for ; i < len(factors); i++ {
		f := factors[i]
		lcm *= ints.Pow64(f.Prime, int64(f.Exponent))
	}
	return lcm
}

// RadInt returns the radical of integer n.
func RadInt(n int) int {
	if 1 == n {
		return 1
	}
	factors := Factorize(int64(n))
	var r int = 1
	for _, f := range factors {
		r *= int(f.Prime)
	}
	return r
}

// RadInt64 returns the radical of integer n.
func RadInt64(n int64) int64 {
	if 1 == n {
		return 1
	}
	factors := Factorize(n)
	var r int64 = 1
	for _, f := range factors {
		r *= f.Prime
	}
	return r
}