RubyのPrimeクラスを使う

競技プログラミングやってた時は、C++がメイン、Javaがサブ(文字列処理、BigIntegert用)で、素数判定を実装してましたが、先日、RubyにはPrimeクラスが用意されていてることを知りました。そこで、Primeクラスの使い方をまとめておこうと思います。

結構使いやすかったのですが、競技プログラミングで使う場合は、どの程度の大きさまで大丈夫そうか、パフォーマンスの測定をしておいた方が良いと思います。
参考

➜  ~  ruby --version
ruby 2.2.3p173 (2015-08-18 revision 51636) [x86_64-darwin15]

RubyのPrimeクラスを使うにはprimeをロードする必要があります。

require 'prime'

##Nが素数かどうかの判定

prime?(value, generator = Prime::Generator23.new) -> bool

n = 83
puts("#{n} is prime number") if Prime.prime?(n) #=> 83 is prime number

##素数の列挙
素数の列挙にはeachを使います。upper_boundがnil(デフォルトがnilなので何も書かない)場合は、無限に列挙します。素数列は昇順になります。

each(upper_bound = nil, generator = EratosthenesGenerator.new) {|prime| ... } -> object[permalink][rdoc]
each(upper_bound = nil, generator = EratosthenesGenerator.new) -> Enumerator

###素数判定表

table = Array.new(N+1, false) #配列のindexは0 origin
Prime.each(N) {|prime| table[prime] = true }
#[Finished in 0.59s] N = 1000000

###N以下の素数列
競技プログラミングだとある数以下の素数列を始めに生成しておくことが多いですが、to_aメソッドを使えば簡単に素数配列が作れます。

primes = Prime.each(N).to_a
#[Finished in 0.499s] #N = 1000000

#N以下の双子素数列
Prime.each(N).each_cons(2).select{|p,r| r-p == 2}

###L以上H以下の素数列
毎回、素数列をループして調べても良いですが、L, Hが大きくなるとO(H)の計算量がかかって効率が悪くなります。昇順の素数列があれば、２分探索でL以上H以下の素数列(スライスすべきインデクス)を求めることができます。

C++ならstd::lower_bound, std::upper_boundを使えば良いのですが、残念ながらRubyにはそれ相当のものが(たぶん)ないので実装しなければなりません。境界条件を間違えそうなので、lower_bound, upper_boundが必要な場合は、素直にC++を使った方が良いような気がします... -> Array#bsearch_index, Range#bsearchのfind-minimum モードで同等のものが実現できます。

• 似たようなメソッドでArray#bsearchというのもありますが、これはindexではなく要素を返すので注意.
• Array#bsearch_index, Range#bsearchはレンジ外(C++でいうところのa.end())の場合nilを返します。C++と同じような挙動にしたいならidx.nil? ? a.size : idxとしておきます。

gist:bound.rb

def lowerBound(a, key)
    idx = (0...a.size).bsearch { |i| a[i] >= key }
    #idx = bsearch_index { |e| e >= key } #Ruby 2.3 and later
    idx.nil? ? a.size : idx
end
def upperBound(a, key)
    idx = (0...a.size).bsearch { |i| a[i] > key }
    #idx = bsearch_index { |e| e > key } #Ruby 2.3 and later
    idx.nil? ? a.size : idx
end
upperBound(primes, H) - lowerBound(primes, L) #部分素数列の個数
primes[lowerBound(primes, L)...upperBound(primes, H)] #部分素数列

自力実装版

def lowerBound(a, key)
    lb = -1; ub = a.length
    while ub - lb > 1
        mid = (lb + ub) / 2
        if a[mid] >= key
            ub = mid
        else
            lb = mid
        end
    end
    ub
end
def upperBound(a, key)
    lb = -1; ub = a.length
    while ub - lb > 1
        mid = (lb + ub) / 2
        if a[mid] <= key
            lb = mid
        else
            ub = mid
        end
    end
    ub
end

###始めのn個, n番目の素数
アドホックにPrime.each.take(n)としても良いですが、クエリ毎にやると効率が悪いので、あらかじめ十分な大きさの素数列を作っておいて、array[0...n]を使うことの方が多いでしょう。

##始めのn個の素数
ary = Prime.each.take(n).to_a #アドホッックにn個
ary = primes[0...n] #Prime.each.take()やPrime.each()で大きめの素数列を作っておく
##n番目の素数
Prime.each.take(n).last
primes[n-1]

尚、素数定理によると、x以下の素数の個数は、

 \frac{x}{\ln x}

で概算できます。

##素因数分解する
prime_divisionで素因数分解、int_from_prime_divisionで逆演算ができる。

prime_division(value, generator= Prime::Generator23.new) -> [[Integer, Integer]]
int_from_prime_division(pd) -> Integer[permalink][rdoc]

int_from_prime_divisionは逆演算をすると書きましたが、単純に $\Pi p^{e}$しているだけなので、素因数に分解されている必要はありません。

a = Prime.prime_division(454085) #=> [[5, 1], [197, 1], [461, 1]]
Prime.int_from_prime_division(a) #=> 454085
Prime.int_from_prime_division([[2, 2], [4, 1], [10, 2]]) #=>1600