Closed2022/03/18にクローズ4

Elixirでエラトステネスのふるいを実装する

Elixirで「エラトステネスのふるい」を実装したい。

使用イメージ

iex> Eratosthenes.is_prime?(120)
false
iex> Eratosthenes.is_prime?(127)
true

要求する仕様は

初期化関数などは呼び出したくない(__use__の定義などは可、呼び出す関数を増やしたくない)
素数表は動的に生成したい
生成した素数表は再利用したい
素数表は再生成したい

問題は、どうやってElixirのモジュール内部にエラトステネスのふるいで作成した素数表を持たせるか。
そもそも、モジュールに動的に生成した素数表を持たせるべきなのか。
外部ファイルとして吐き出して、それを読み込むようにするか？

暗黙的な情報を無くすという観点だと、変数に格納してその変数を扱う関数を定義する方が良いかも知れない。

# 素数表の生成関数を定義する場合のイメージ
iex> primes = Eratosthenes.make(300)
[1,3,5,7,11...] # 素数表
iex> Eratosthenes.is_prime?(127, primes)
true

# 変数を使わないイメージ例1(ただし素数表の再利用が効かない)
iex> Eratosthenes.is_prime?(127, Eratosthenes.make(300))
true

# 変数を使わないイメージ例2(こちらも素数表の再利用が効かない)
iex> Eratosthenes.make(300) |> Eratosthenes.is_prime?(127)
true

素数表を動的に生成する意味は何か？
素数表の結果は求める値の最大値が決まっていれば常に同じになるため、モジュールの属性に1000までの素数表を持たせておけば都度計算する必要は無い。
デメリットとして、メモリの消費が増えることが挙げられる。
100までの素数表で充分であれば1000までの素数表は巨大なため。

一度、生成関数を持たせたモジュールでエラトステネスのふるいを実装し、その後モジュールに保持する方法を考える

Endo Shogo

エラトステネスの篩の実装

エラトステネスの篩の処理は次の通りになります。

求める範囲の最大値+1(= Nとおく)と同じ要素数の配列を用意し、配列の値をすべてtrueにします。この配列は添字1から始めるものとします。
値1(= p)から順番に、配列[p]の値がtrueかどうかを判定してtrueの場合のみ処理3を実行します。
値pが素数の場合、pのn倍以上の値をすべて削除します(n>1)。
値pが√N を超えるまで、2~3を繰り返します。

アクセス速度を重視するため、素数表はタプルの形で作る。
elem/1で取得して put_elem/1で更新する。
問題は目視では、どの値がtrueかfalseか分かりにくいこと。
いきなり大きい値で素数表を作らず、小さい値でテストしてから大きい素数表を作る。

# 1~10までの素数表(0はfalseで埋める)
iex> primes = {false, true, false, true, false, true, false, true, false, false, false}
iex> elem primes, 1
true
iex> elem primes, 9
false

Endo Shogo

ざっくり実装してみた

defmodule Eratosthenes do
  def is_prime?(number, primes) do
    elem(primes, number)
  end

  def make(size) do
    sieve(Tuple.duplicate(true, size+1), trunc(:math.sqrt(size)))
  end

  defp sieve(tuple, limit, index \\ 2) when limit >= index do
    cond do
      elem(tuple, index) -> Enum.reduce(index..tuple_size(tuple)//index, tuple, &Kernel.put_elem(&2, &1, false)) |> sieve(limit, index+1)
      true -> sieve(tuple, limit, index+1)
    end
  end
  defp sieve(tuple, _limit, _index), do: tuple
end

Endo Shogo

モジュール名などを見直してGitHubにpushしました。

TODO:

document追加
テストケース追加
もう少しモジュール名を見直してHexに登録
速度を比較してより高速な方法が無いか調査

このスクラップは2022/03/18にクローズされました