Prime Factorization

In this lesson you will learn how to factor a number into primes in Go, covering a number-theory algorithm built on loops. This is for anyone searching for "Go prime factorization implementation".

Prime factorization means expressing a number as a product of primes. Try dividing by 2, then 3, and so on; whenever a divisor works, keep dividing by it.

The sample code starts at d := 2 and, for as long as n divides by d, records it with factors = append(factors, d) and divides with n /= d. When it no longer divides, d increases by one, repeating until n reaches 1.

A common stumbling block for beginners is the nested loop structure. The outer loop raises the divisor d while the inner loop keeps dividing for as long as it can - grasp that two-stage combination and the whole algorithm falls into place.

It is an important idea spanning mathematics and computer science that underpins the security of cryptography such as RSA. Since 1 divides everything, it is excluded from prime factorization.

📖 Reference code

package main

import "fmt"

func primeFactors(n int) []int {
	factors := []int{}
	d := 2
	for n > 1 {
		for n%d == 0 {
			factors = append(factors, d)
			n /= d
		}
		d++
	}
	return factors
}

func main() {
	fmt.Println(primeFactors(60))
	fmt.Println(primeFactors(97))
}

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Go directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).