library prime

要約

素数や素因数分解を扱うライブラリです。

ライブラリの中心にあるのは Prime クラスで、これは素数全体を表すシングルトンです。また、素数性と素因数分解に関するメソッドを Integer に追加します。さらに、 Prime クラスの機能を実現するための低水準のクラスも幾つか提供されています。

require 'prime'

Prime.each(100) do |prime|
  p prime #=> 2, 3, 5, 7, 11, ..., 97
end

2.prime? #=> true
4.prime? #=> false

Prime のメソッドは内部で低水準の疑似素数生成器を使用します。生成器は擬似素数の列挙方法の実装を提供します。また列挙状態や列挙の上界を記憶する機能もあります。更に、 Enumerator と互換性のある外部イテレータでもあります。

状況に応じて適切な疑似素数生成アルゴリズムは異なるので、いくつかの生成器の実装が用意されています。 Prime::PseudoPrimeGenerator は生成器の基底となるクラスです。

Prime::EratosthenesGenerator: エラトステネスの篩いを使用します。
Prime::TrialDivisionGenerator: 試行除算法を使用します。
Prime::Generator23: 2 と 3 で割り切れない全ての正の整数を生成します。この数列は素数の数列としては使い物になりません。しかし、他の生成器より速く、メモリの使用量も少ないという特徴があります。そのため、それほど大きくなくて、素数の要素を多く持つ整数の因数分解に向いています。

Prime クラスの各メソッドは、一般的な用途を想定して適切な生成器を使用します。ユーザーは必要に応じて特定の生成器実装を使用するようにオプション引数を設定することもできます。また、ユーザーは独自の生成器を実装することもできます。

Prime	素数全体を表します。
Prime::PseudoPrimeGenerator	擬似素数列の列挙子のための抽象クラスです。
Prime::EratosthenesGenerator	Prime::PseudoPrimeGenerator の具象クラスです。素数の生成にエラトステネスのふるいを使用しています。
Prime::Generator23	2と3と、3 より大きくて 2 でも 3 でも割り切れない全ての整数を生成します。
Prime::TrialDivisionGenerator	Prime::PseudoPrimeGenerator の具象クラスです。素数の生成に試行除算法を使用しています。

Ruby1.8 との互換性のためのモジュールです。 Prime オブジェクトにRuby 1.8互換の機能を与えます。

forwardable	クラスやオブジェクトに、メソッドの委譲機能を追加するためのライブラリです。
singleton	Singleton パターンを扱うためのライブラリです。