素因数分解

 1func factorize(n int) map[int]int {
 2	pf := map[int]int{}
 3	for i := 2; i*i <= n; i++ {
 4		for n%i == 0 {
 5			pf[i]++
 6			n /= i
 7		}
 8	}
 9	if n != 1 {
10		pf[n] = 1
11	}
12	return pf
13}
14

 1type spft []int
 2
 3func newSmallestPrimeFactorTable(n int) *spft {
 4	pt := make(spft, n+1)
 5	for i := 0; i <= n; i++ {
 6		pt[i] = i
 7	}
 8	for m := 2; m*m <= n; m++ {
 9		if pt[m] < m {
10			continue
11		}
12		for i := m * m; i <= n; i += m {
13			if pt[i] == i {
14				pt[i] = m
15			}
16		}
17	}
18	return &pt
19}
20
21func (f spft) factorize(a int) map[int]int {
22	pf := map[int]int{}
23	for a != 1 {
24		pf[f[a]]++
25		a /= f[a]
26	}
27	return pf
28}
29