シクシク素数列 Advent Calendar 2018 golang編

シクシク素数列 Advent Calendar 2018 の 22日目になります。

golangでの素数算出については、公式にgoroutineとchannelを利用した方式があります。
https://golang.org/doc/play/sieve.go

これを流用して、素数からシクシク素数を抜粋しました。
テストしやすいように、素数算出箇所はmain関数から取り出しています。

プログラム

prime49.go

package main

import (
	"os"
	"strconv"
	"strings"
)

func Generate(ch chan<- int) {
	for i := 2; ; i++ {
		ch <- i
	}
}

func Filter(in <-chan int, out chan<- int, prime int) {
	for {
		i := <-in
		if i%prime != 0 {
			out <- i
		}
	}
}

func Execute(max int) string {
	list := []string{}
	ch := make(chan int)
	go Generate(ch)
	for i := 0; len(list) < max; i++ {
		prime := <-ch
		ch1 := make(chan int)
		go Filter(ch, ch1, prime)
		ch = ch1
		// シクシク素数列のみ記録
		if s := strconv.Itoa(prime); strings.ContainsAny(s, "4|9") {
			list = append(list, s)
		}
	}
	return strings.Join(list, ",")
}

func main() {
	max := 0
	if len(os.Args) > 1 {
		max, _ = strconv.Atoi(os.Args[1])
	}
	print(Execute(max), "\n")
}

出力例

$ go run prime49.go 9
19,29,41,43,47,59,79,89,97

$ go run prime49.go 10
19,29,41,43,47,59,79,89,97,109

$ go run prime49.go 100
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319

テストコード

prime49_test.go

package main

import (
	"fmt"
	"testing"
)

func TestExecute(t *testing.T) {
	tests := []struct {
		num    int
		result string
	}{
		{0, ""},
		{1, "19"},
		{2, "19,29"},
		{3, "19,29,41"},
		{9, "19,29,41,43,47,59,79,89,97"},
		{10, "19,29,41,43,47,59,79,89,97,109"},
		{99, "19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297"},
		{100, "19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319"},
		{101, "19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319,1399"},
	}
	for _, tt := range tests {
		description := fmt.Sprintf("input:[%v]", tt.num)
		t.Run(description, func(t *testing.T) {
			msg := Execute(tt.num)
			if msg != tt.result {
				t.Fatal("出力値が異なる[", msg, "][", tt.result, "]")
			}
		})
	}
}

別プログラム

goroutine と channel を利用しない場合で書いてみました。
単に、構造体とメソッド、無名関数、flagを利用してみたかったというのもあります。
素数算出においては、あらかじめ「2」を素数として記録しておき、以降は奇数のみを確認対象として実施しています。シクシク素数の抽出は最初のバージョンと同じです。

prime49.go

package main

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

type Prime4949 struct {
    PrimeNumbers [] int
    List49 [] string
}

func main() {
    var nCount = flag.Int("N", 9, "N=9")
    var nMax = flag.Int("MAX", 100, "MAX=100")
    var isMsgOpt = flag.Bool("v", false, "v=true")
    flag.Parse()
    if *nCount > *nMax {
        *nCount = * nMax
    }

    var pri Prime4949
    msg := pri.Execute(*nCount)
    if *isMsgOpt {
        msg = fmt.Sprintf("N=[%v] :", *nCount) + msg
    }
    fmt.Println(msg)
}

func (pri *Prime4949) Execute(nCount int) string {
    const firstPrimeNum = 2
    pri.PrimeNumbers = []int{firstPrimeNum}
    pri.List49 = []string{}
    for i := firstPrimeNum+1; len(pri.List49) < nCount; i += 2 {
       pri.addPrime(i)
    }
    msg := strings.Join(pri.List49 ,",")
    return msg
}

func (pri *Prime4949) addPrime(num int) {
    check := func () bool{
        if num < 2 {
            return false
        }
        isPrime := true
        for _, prime := range pri.PrimeNumbers {
            if num % prime == 0 {
                isPrime = false
                break
            }
        }
        return isPrime
    }
    if check() {
        pri.PrimeNumbers = append(pri.PrimeNumbers, num)
        if s := strconv.Itoa(num); strings.ContainsAny(s, "4 | 9") {
            pri.List49 = append(pri.List49, s)
        }
    }
}

出力例（別プログラム）

$ go run prime49.go -N 9
19,29,41,43,47,59,79,89,97

$ go run prime49.go -N 10
19,29,41,43,47,59,79,89,97,109

$ go run prime49.go -N 100
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319