Elixir は先月うまくいかなくてめげてしまったので、ここ最近は Go 言語に手を出している。ま、Web ページを見ながら見様見真似でやってるんだけど、言語の雰囲気はなんとなくわかったってところかな。OS ネイティブの実行ファイルが作れるのはいいね。ツールを作って他人に配るのにはいい。goroutine はよくわかんない。
で、ちょっと整数の素因数分解をするプログラムを作ってみた。
package main
import (
"fmt"
"os"
"flag"
"strconv"
)
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
}
func primeFactors(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 main() {
Usage := func() {
fmt.Fprintf(os.Stderr, "Usage: %s \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 := primeFactors(n)
s := fmt.Sprintf("%v", f)
l := len(s) fmt.Println(s[1:l-1])
}
}
コンパイルせずにそのまま実行するには go run コマンド。
^o^ > go run primefactors.go 12345 3 5 823
コンパイルするには go build コマンド。
^o^ > go build primefactors.go ^o^ > ls primefactors.exe primefactors.go ^o^ > primefactors 12345 3 5 823