先日参加させていただいた勉強会 Go&Elixirでつくる分散アプリケーションにて
エラトステネスの篩というアルゴリズムをGo言語で実装した例を紹介していました。
(実はその勉強会で初めてこのアルゴリズムを知りました ^^;)

エラトステネスの篩はある指定された整数以下の素数を見つけるためのアルゴリズムとなります。
詳細はWikipediaをご参照ください

勉強会での例ではGoのチャンネルを使って実装されていたので、
Elixirでは子プロセスを生成し、そちらで値のフィルタリングをしていくという
方法で実装みたいと思います。

実装

erastosthenes.exs

defmodule Erastosthenes do

  def sieve(prime, next, last?) do
    receive do
      n when rem(n, prime) == 0 ->
        sieve(prime, next, last?)
      n ->
        send next, n
        next = if last? do
          # 自身が最後の篩だったら次の篩を生成する
          {pid, _} = spawn_monitor Erastosthenes, :sieve, [n, next, true] 
          pid
        else
          next
        end
        sieve(prime, next, false)
    end
  end

  def output do
    receive do
      n ->
        IO.puts "#{n} is prime."
        output()
    end
  end
end

opid = spawn Erastosthenes, :output, []
{spid, _} = spawn_monitor Erastosthenes, :sieve, [2, opid, true]

2..100
|> Stream.map(&(send spid, &1))
|> Enum.to_list

それぞれの篩は以下の値を保持するようにしています
- 素数
- 次の篩、もしくは出力用プロセスのpid
- 自身が最後の篩かどうか

sieve を子プロセスとしてどんどん生成いき、
大元から渡された値を篩にかけていきます。
渡された値が自身の素数で割り切れなかったら次の素数の篩に送ります。
もし自身が最後の篩の場合、割り切れなかった値は
素数なので次の素数の篩を生成しています。

実行結果がこちら

$ iex
iex(1)> c"erastosthenes.exs"
3 is prime.
5 is prime.
7 is prime.
11 is prime.
13 is prime.
17 is prime.
19 is prime.
23 is prime.
29 is prime.
31 is prime.
37 is prime.
41 is prime.
[Erastosthenes]
43 is prime.
47 is prime.
53 is prime.
59 is prime.
61 is prime.
67 is prime.
71 is prime.
73 is prime.
79 is prime.
83 is prime.
89 is prime.
97 is prime.

親プロセスでreceiveしていないため、iexで実行しないと
全部出力するまえに実行が終了してしまうのでわざわざiexで実行しています

また最初の素数である2だけは最初に篩を作ってあげる必要があるので、
出力に表示されていないです

まとめ的な何か

今回は生spawnを使って書いてみましたが、
sieve関数で状態を保持する必要があるのでAgentを使ったほうがよかったかなと
思っています。

また出力のとこも微妙になってしまったのがなんとも残念です。
(Elixir力が足りない。。。)

何かご指摘等いただけますと嬉しいです。

Elixirでエラトステネスの篩を実装してみた

実装

まとめ的な何か