はじめに
上で紹介したアルゴリズムの中に「Wheel Factorization」があります。
これをもう少し詳しく説明していこうと思います。
Wheel Factorizationとは
Wheel Factorizationは試し割り法をより効率的にする手法です。
素数判定アルゴリズムとして有名な試し割り法は、探索する数$N$について、$2\le k \lt N$の整数の$k$でひたすら割るアルゴリズムです。つまり計算量が$O(N)$になり、十分大きな整数が素数かどうかを判定するとなると、非常に時間がかかってしまいます。この$k$の範囲全てを割るのは効率的にも悪いため、できるだけ減らそうという手法がWheel Factorizationになります。
Wheel Factorizationでは、まず小さな素数のリスト$P$を用意します。簡単に、$P=\{2,3,5\}$としましょう。
このとき、この素数リスト全てを約数にもつ整数$X=\Pi_{P}x$(例の場合、$X=2\times 3\times 5=3$)のリスト(円)を作ります。
このリストから、1および$P$のいずれかで割れる数($P$の値そのものは除く)にチェックしていきます(赤色)
このとき、未チェックの要素は全て素数、つまり$\{2,3,5,7,11,13,17,19,23,29\}$が残ります。
続いて、$X$を加算した要素を輪のリストの各要素に追加し、さきほどと同様に$P$のいずれかを約数に持つリストにチェックしていきます。
次も同様にすると、
となり、$7\le k\le X+7$に着目すると輪に周期性が現れるのが確認できます。この間隔は$\mathrm{inc}=\{4,2,4,2,4,6,2,6\}$となります。
つまり、$\mathrm{inc}$を順番に加算していくことで表される数だけ試し割りに使う数にすればよい、これがWheel Factorizationの手法になります。
実装
Pythonで実装すると次のようになります。
import itertools
import operator
# 既知の素数
P = (2, 3, 5)
# はじめの素数
startp = 7
# 総乗を求める
*_, X = itertools.accumulate(P, operator.mul)
X += 1
# [startp, X+startp]のリスト
p_list = list(range(startp+1,X+startp+1))
# 周期を作る
p_temp = [startp]
inc = []
for i, n in enumerate(p_list):
divisible = False
for _p in P:
if n % _p == 0:
divisible = True
break
if not divisible:
# 割り切れない場合、nから直前の割り切れなかった数を引く
inc.append(n - p_temp[-1])
p_temp.append(n)
print(inc)
[4, 2, 4, 2, 4, 6, 2, 6]
Pとstartpを変えればより大きな$\mathrm{inc}$が作れます。ただし、その周期の大きさは$X$と同程度になるので注意してください。
どのくらい探索回数が減るのか
Wheel Factorizationは試し割に使う数を減らせることができます。言い換えれば、$\mathrm{inc}$が求まれば$P$の要素の倍数については調べる必要がなくなるわけです。
いくつかの数で比較してみましょう。$N=198491317$(11000000番目の素数です)を探索する場合、$\sqrt{N}$までの数で割ればいいので、試し割りは$14090$回探索されます。
Wheel Factorizationについて、$P$を様々なケースで探索すると、次のようになります。
| P | 配列の要素数 | 探索回数 | 試し割と比べて(倍) |
|---|---|---|---|
| [2,3] | 2 | 4696 | 3.00 |
| [2,3,5] | 8 | 3757 | 3.75 |
| [2,3,5,7] | 48 | 3220 | 4.38 |
| [2,3,5,7,11] | 480 | 2927 | 4.81 |
| [2,3,5,7,11,13] | 5760 | 2701 | 5.22 |
| [2,3,5,7,11,13,17,19] | 92160 | 2543 | 5.54 |
| [2,3,5,7,11,13,17,19,23] | 1658880 | 2410 | 5.85 |
| [2,3,5,7,11,13,17,19,23,27] | 36495360 | 2305 | 6.11 |
(29以上は私のPCが持ちませんでした)
探索回数はそこまで大幅に減少しません。その一方で、配列の要素数は指数的に増加します。大きくすればいい、ということではないですね。
実際、探索回数は計算量で表記すると$O(N/(\log\log N))$1になります、分母の発散は非常に遅いため、割と小さい$P$の方が効率が良いわけです。
おわりに
Wheel Factorizationについて紹介しました。$\{4, 2, 4, 2, 4, 6, 2, 6\}$は割と覚えやすい数列なので、2,3,5の倍数を飛ばしたいときは是非つかってみるのをおすすめします。
ただ、この手法は結局$N$に比例して大きくなるので、使える場はわりと限られますが。