素数を探すライブラリ prime_finder gem

エラトステネスのふるいを使って、与えられた数の上限まで毎回計算してます。

利用範囲の素数を一気に求めておいてから配列に入れておき、それを使うのがよいでしょうね。

使い方

求めたい数の下限上限を入れます。

PrimeFinder.new.find_primes(lower, upper)

素数の配列が返ります。

速度

基準数から1000に含まれる素数を求めます。
MacBook Pro w/Retina 13" Late 2013(Intel Core i5 2.4GHz)で試しました。
最後に表示しているのはミリ秒です。

$ ruby -rprime_finder -e 't = Time.now; p PrimeFinder.new.find_primes(10000, 11000); p (Time.now - t) * 1000'
[10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 10973, 10979, 10987, 10993]
3.137
$ ruby -rprime_finder -e 't = Time.now; p PrimeFinder.new.find_primes(1000000, 1001000); p (Time.now - t) * 1000'
[1000003, 1000033, 1000037, 1000039, 1000081, 1000099, 1000117, 1000121, 1000133, 1000151, 1000159, 1000171, 1000183, 1000187, 1000193, 1000199, 1000211, 1000213, 1000231, 1000249, 1000253, 1000273, 1000289, 1000291, 1000303, 1000313, 1000333, 1000357, 1000367, 1000381, 1000393, 1000397, 1000403, 1000409, 1000423, 1000427, 1000429, 1000453, 1000457, 1000507, 1000537, 1000541, 1000547, 1000577, 1000579, 1000589, 1000609, 1000619, 1000621, 1000639, 1000651, 1000667, 1000669, 1000679, 1000691, 1000697, 1000721, 1000723, 1000763, 1000777, 1000793, 1000829, 1000847, 1000849, 1000859, 1000861, 1000889, 1000907, 1000919, 1000921, 1000931, 1000969, 1000973, 1000981, 1000999]
308.74499999999998
$ ruby -rprime_finder -e 't = Time.now; p PrimeFinder.new.find_primes(100000000, 100001000); p (Time.now - t) * 1000'
[100000007, 100000037, 100000039, 100000049, 100000073, 100000081, 100000123, 100000127, 100000193, 100000213, 100000217, 100000223, 100000231, 100000237, 100000259, 100000267, 100000279, 100000357, 100000379, 100000393, 100000399, 100000421, 100000429, 100000463, 100000469, 100000471, 100000493, 100000541, 100000543, 100000561, 100000567, 100000577, 100000609, 100000627, 100000643, 100000651, 100000661, 100000669, 100000673, 100000687, 100000717, 100000721, 100000793, 100000799, 100000801, 100000837, 100000841, 100000853, 100000891, 100000921, 100000937, 100000939, 100000963, 100000969]
33700.843999999997

基準数が1万だと3ms、100万だと300ms、1億だと30秒かかります。O(n)のオーダーの計算であることがよく分かります。1000万までならばともかく、億になると毎回計算させるのは辛いですね。