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

クラス

同時にrequireされるライブラリ

追加・再定義されるメソッド

Integer#prime? Integer#prime_division Integer.each_prime Integer.from_prime_division