自然数を素因数分解する

primefactors.go

package main

import (
	"fmt"
	"os"
	"flag"
	"strconv"
	"strings"
)

func main() {
	Usage := func() {
		fmt.Fprintf(os.Stderr, "Usage: %s <N>\n", os.Args[0])
	}
	opt_help := flag.Bool("h", false, "Help message")
	flag.Parse()

	if *opt_help || flag.NArg() < 1 {
		Usage()
		os.Exit(0)
	}
	n, err := strconv.Atoi(flag.Arg(0))
	if err != nil {
		fmt.Fprintln(os.Stderr, "Invalid argument.")
		os.Exit(1)
	}
	if n < 2 {
		fmt.Println("Nothing prime factors.")
	} else {
		f := factors(n)
		s := make([]string, len(f))
		for i, p := range f {
			s[i] = strconv.Itoa(p)
		}
		fmt.Println(strings.Join(s, " "))
	}
}

func factors(n int) []int {
	// n が合成数だと仮定すると、可能性として考えられる最大の素因数は n/2。
	ps := primes(n / 2)
	// n/2 以下の素数の中から素因数を探す。
	facts := make([]int, 0)
	for _, p := range ps {
		for n != 1 {
			if n % p == 0 {
				facts = append(facts, p)
				n = n / p
			} else {
				break
			}
		}
	}
	// n/2 までに素因数が見つからない場合、n 自身が素数。
	if len(facts) == 0 {
		facts = append(facts, n)
	}
	return facts
}

func primes(n int) []int {
	p := make([]bool, n + 1)
	// スライス p はゼロ値（false）で初期化されるので、2 と 3 以上の奇数だけ true に初期化する。
	if 2 < n {
		p[2] = true
		for i := 3; i <= n; i += 2 {
			p[i] = true
		}
	}
	// 3 以上の奇数を順にふるいにかける。
	for i := 3; i * i < n; i += 2 {
		if p[i] {
			for j := i + i; j <= n; j += i {
				p[j] = false
			}
		}
	}
	// 素数だけ pn に追加。
	pn := make([]int, 0)
	for i := 2; i <= n; i++ {
		if p[i] {
			pn = append(pn, i)
		}
	}
	return pn
}