Elmでシクシク素数

こちらは シクシク素数列 Advent Calendar 2018 11日目の記事です。

ルール(転載)

• 数値に4か9を含む素数をシクシク素数と呼ぶことにします
  • 19とか41とか149とか。
• 標準入力として正の整数 N を与えたら N 番目までのシクシク素数を半角カンマ区切りで標準出力してください
  • 例 N = 9 の場合、 19,29,41,43,47,59,79,89,97
• N は最大で 100 とします

実装

Elmはフロントエンドの関数型言語であるため、本来は標準入力であるところをスライダーによる入力としました。

Ellie-appによるデモ ←デモをおいておきますので自由に使ってみてください。

ソースコードを貼っておきます。解説は下の方で。

module Main exposing (main)

import Browser exposing (Document, document)
import Html exposing (Html, div, input, li, text, ul)
import Html.Attributes as A
import Html.Events exposing (onInput)


constMax : Int
constMax =
    100


main =
    Browser.document
        { init = init
        , view = view
        , update = update
        , subscriptions = subscriptions
        }


subscriptions : Model -> Sub Msg
subscriptions model =
    Sub.none


type alias Model =
    { n : Int
    }


init : () -> ( Model, Cmd Msg )
init _ =
    ( { n = 9 }, Cmd.none )


type Msg
    = NoOp
    | UpdateMax Int


update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
    case msg of
        NoOp ->
            ( model, Cmd.none )

        UpdateMax n ->
            ( { model | n = n }, Cmd.none )


view : Model -> Document Msg
view model =
    { title = "シクシク素数"
    , body = viewBody model
    }


viewBody : Model -> List (Html Msg)
viewBody model =
    [ div []
        [ input [ A.type_ "range", A.min "1", A.max <| String.fromInt constMax, A.value <| String.fromInt model.n, onInput inputMax ] []
        , text <| String.fromInt model.n
        ]
    , show49Primes model
    ]


inputMax : String -> Msg
inputMax v =
    case String.toInt v of
        Just n ->
            if n > 0 && n <= constMax then
                UpdateMax n

            else
                NoOp

        Nothing ->
            NoOp


show49Primes : Model -> Html Msg
show49Primes model =
    div []
        [ list49Primes model.n
            |> List.map (\n -> String.fromInt n)
            |> String.join ","
            |> text
        ]


list49Primes : Int -> List Int
list49Primes n =
    list49Primes_ n 2 []


list49Primes_ : Int -> Int -> List Int -> List Int
list49Primes_ n i xs =
    case n of
        0 ->
            List.reverse xs

        _ ->
            if isPrime i && hasFourOrNine i then
                list49Primes_ (n - 1) (i + 1) (i :: xs)

            else
                list49Primes_ n (i + 1) xs


isPrime : Int -> Bool
isPrime n =
    List.range 2 (floor <| sqrt <| toFloat n)
        |> List.all (\i -> modBy i n /= 0)


hasFourOrNine : Int -> Bool
hasFourOrNine n =
    String.fromInt n
        |> (\s -> String.contains "4" s || String.contains "9" s)

解説

メインロジックの部分を解説しますね。
list49Primes という関数でシクシク素数列を生成しています。

list49Primes : Int -> List Int
list49Primes n =
    list49Primes_ n 2 []


list49Primes_ : Int -> Int -> List Int -> List Int
list49Primes_ n i xs =
    case n of
        0 ->
            List.reverse xs

        _ ->
            if isPrime i && hasFourOrNine i then
                list49Primes_ (n - 1) (i + 1) (i :: xs)

            else
                list49Primes_ n (i + 1) xs

最初の list49Primes は list49Primes_ という関数に初期値を与えるだけのものです。

関数型言語であるElmでは変数への代入ができず、 while などのループが使えません(そもそも while がありません)。そのため既定の個数の素数が見つかるまでループするには再帰関数を使うことになります。

list49Primes_ という関数は末尾再帰関数になっていて、シクシク素数が見つかったら n を一つ減らしてリストに素数を追加します。（末尾再帰にする必要はありませんが、ただの好みです。）
スキップする部分は省略しますが、実行イメージはこんな感じです。リストの先頭に要素を追加して最後にひっくり返してます。

list49Primes_ 4 19 []
list49Primes_ 3 29 [19]
list49Primes_ 2 41 [29, 19]
list49Primes_ 1 43 [41, 29, 19]
list49Primes_ 0 44 [43, 41, 29, 19]
[19, 29, 41, 43]

偶数をスキップするなどすればもっと効率化できますが、100個までならこれでも十分だと思います。

最後に

Elmに興味を持った方がいらっしゃれば、Elmアドベントカレンダーもありますのでぜひどうぞ。