Code for different number theory algorithms in golang ofc

main.go

package main

import "fmt"

func gcd(a, b int) int {
	var fun func(int, int) int

	fun = func(l, h int) int {
		r := h % l
		if r == 0 {
			return l
		}

		if r == 1 {
			return r
		}

		return fun(r, l)
	}

	if a > b {
		return fun(b, a)
	}

	return fun(a, b)
}

// inefficient
func primes(n int) []int {
	primes := []int{1}

	mul := 1

	m := n

	for i := 2; ; i += 1 {
		r := m % i
		if r != 0 {
			continue
		}

		primes = append(primes, i)

		if i == m {
			return primes
		}

		mul *= i

		m = n / mul

		i = 2
	}
}

func main() {
	a, b := 16, 72
	fmt.Println(gcd(a, b))

	fmt.Println(primes(9488485))
}