シクシク素数列 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