エラトステネスの篩

エラトステネスの篩（ふるい）とは、素数を求めるアルゴリズムである。

2000年以上前に考案された方法ながら、ユークリッドの互除法と並んで現在でも応用されている重要な方法である。

概要

エラトステネスとは紀元前3世紀頃の学者であり、地球の大きさを誤差数%以内で推定した事などで有名な人物である。エラトステネスの篩はそんな彼が考案したとされ、素朴な方法ながらも確実にすべての素数を求めることができる、優秀なアルゴリズムである。合成数が次々に消去され、素数が残っていく様が「ふるいにかける」ようであるからこの名前がついた。以下がそのアルゴリズムの概略である。

自然数に対するアルゴリズム

1. 自然数を並べ、初めに1をマークし、次に2をマークして2の倍数を消去する。
2. 次に残った数で一番小さい3をマークし3の倍数を消去する。
3. 次に残った数で一番小さい5をマークし…といった作業を繰り返す。

以上の作業を繰り返すことで素数を求めることができる。以下は100までの表。赤色が素数である。

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

この表から、2,3,5,7,11,13,17,…が素数であることが分かった。

利点

• nまで作業が終わればn²までの素数が漏れなく求まる。この表で言えば10以下の素数、つまり7を見つける手順が終わった時点で100までの素数すべてが明らかになる。
• 仮に素数を飛ばしてしまっても合成数で素数が消去されることは無いので、後に検算をした際にその素数から追加で消去していけば正しい表が得られることも重要な利点である。
• 素数pの倍数を消去する際、p×2からp×(p-1)までの数は消去されているので、p×pから消去していけば処理が早くなる。

欠点

• 素数をくまなく求めることはできるが、この方法から素数の現れる法則を見出すことはできない。素数かどうかを判定する方法ではなく、あくまで素数をリストアップする方法である。
• マークした素数以上の全ての数を毎回チェックして回る必要があるため時間がかかる。工夫しないとN以下の素数を調べるのにO(N√N)くらいの時間がかかるらしい。工夫次第でO(N)に近づいていくがそれを下回ることは無いと思われる。
• 途中で表を大きくしようとしたい場合、追加した分を2の倍数から埋め直す必要がある。
• 大きな素数を求める場合でも2から始めないと数え漏れが出てしまうので融通が利かない。

関連動画

関連項目

• 算数、数学
• アルゴリズム
• 数学関連用語の一覧
• 自然数
• 素数

---

応用

以上が義務教育で教わる内容である。

以下、応用例としてガウス整数と多項式について記述する。

ガウス整数に対するエラトステネスの篩

ガウス整数とは、a,bを整数としてz'=a+biで表すことのできる数である。ガウス整数にも素数に対応する概念が存在し、ガウス素数と呼ばれる。ガウス素数は普通の素数と同じで、それ以上素因数分解することができない数である。こちらもエラトステネスの篩で求めることができる。

ガウス整数におけるアルゴリズム

1. 0を中心にマス目状にガウス整数を並べ、0と1,-1,i,-iにマークする。
2. ±(1+i)をマークし、1+iの倍数(1+i)(x+yi)=(x-y)+(x+y)iを消去する。次に±(1-i)の倍数を消去する。
3. 残った数で0に近い±(1+2i)をマークしてその倍数(x-2y)+(x+2y)iを消去する。次に±(2+i)をマークしての倍数を消去する。
4. 以下同じようにして0に近い数から順に±(a+bi)をマークして倍数を消去、±(b+ai)をマークして倍数を消去を繰り返す。
5. マークされた数がガウス素数である。

以下が上記のアルゴリズムで得られたガウス素数の表である。◉がガウス素数。

O

O

O

O

O

◉

O

O

O

O

O

O

O

O

O

O

O

O

O

◉

O

O

O

O

O

O

O

O

O

O

O

◉

O

◉

O

O

O

◉

O

O

O

◉

O

◉

O

O

O

O

O

O

O

O

O

◉

O

◉

O

O

O

◉

O

◉

O

◉

O

◉

O

O

O

◉

O

◉

O

O

O

O

O

◉

O

O

O

O

O

◉

O

O

O

O

O

O

O

◉

O

O

O

O

O

◉

O

O

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

O

O

◉

O

◉

O

O

O

◉

O

O

O

O

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

◉

O

O

O

◉

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

O

O

◉

O

O

O

◉

O

◉

O

O

O

◉

O

O

O

◉

O

◉

O

O

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

O

O

O

O

O

O

◉

O

◉

O

◉

O

◉

O

◉

O

◉

O

◉

O

◉

O

O

O

O

O

O

O

◉

O

O

O

◉

O

◉

O

◉

◉

i

◉

◉

O

◉

O

◉

O

O

O

◉

O

O

O

◉

O

O

O

◉

O

O

O

◉

O

-1

0

1

O

◉

O

O

O

◉

O

O

O

◉

O

O

O

◉

O

O

O

◉

O

◉

O

◉

◉

-i

◉

◉

O

◉

O

◉

O

O

O

◉

O

O

O

O

O

O

O

◉

O

◉

O

◉

O

◉

O

◉

O

◉

O

◉

O

◉

O

O

O

O

O

O

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

O

O

◉

O

◉

O

O

O

◉

O

O

O

◉

O

◉

O

O

O

◉

O

O

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

◉

O

O

O

◉

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

O

O

O

O

◉

O

O

O

◉

O

◉

O

O

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

◉

O

◉

O

◉

O

O

O

O

O

O

O

◉

O

O

O

O

O

◉

O

O

O

O

O

O

O

◉

O

O

O

O

O

◉

O

O

O

O

O

◉

O

◉

O

O

O

◉

O

◉

O

◉

O

◉

O

O

O

◉

O

◉

O

O

O

O

O

O

O

O

O

◉

O

◉

O

O

O

◉

O

O

O

◉

O

◉

O

O

O

O

O

O

O

O

O

O

O

◉

O

O

O

O

O

O

O

O

O

O

O

O

O

◉

O

O

O

O

O

上記の表から1±i、1±2i、2±i、3、3i、4±i、1±4i、…などがガウス素数であることが分かった。

段階2.で2から始めても良いが、次の1±iの倍数の消去の過程で2が消えてしまう。つまり、ガウス整数において2はガウス素数ではないという事がわかる。実際、2=(1+i)(1-i)であり、素因数分解できる。

ガウス素数は美しい模様を描く。整数の素数と比べ均等に分布しており、一定のパターンが存在しているように見える。有限距離以内でガウス素数同士が隣接するかどうかは未解決問題である。

こちらは0を中心に(2n+1)×(2n+1)マスまで終わっていれば少なくとも(4n+1)×(4n+1)マスまでのガウス素数が求まる。また、消去される倍数が正方形の頂点上に並ぶので各ステップで消去される倍数もキレイなパターンを描く。

欠点はやはり時間がかかるところ。途中から表の拡張をするのはかなり難しい。

多項式環に対するエラトステネスの篩

既約多項式とは、それ以上小さな次数の多項式に因数分解できない多項式を指す。多項式環において既約多項式は素数と同様の働きを持つ。同じ多項式でも係数体により既約か可約か変化する。

整数を素数pで割ったあまりで分類すると有限体F_pになる。F_pの元を係数とする多項式f(x)∈F_p[x]を考える。例えば、F₂係数多項式f(x)∈F₂[x]は係数が0または1の多項式である（1+1=0に注意して計算する）。f(x)が既約であるかどうかをエラトステネスの篩を用いて列挙する事で判別できる。

準備として、多項式をその係数のみで表すことにする。例えば、F₂[x]においてx³+x²+1 → 1101、(x+1)(x²+x)=x³+x → 11×110=1010。F₃[x]において(x+2)(2x+1)=2x²+2x+2 → 12×21=222。単純な2進数や3進数とは異なることに注意。

F₂[x]におけるアルゴリズム

1. 多項式を小さい順から列挙し、1にマークする。次にxにマークし、xにx以上の多項式を掛け算して列挙したものを消去する。
2. 次に、残った多項式で一番小さな多項式x+1をマークし、残った多項式をx+1から掛け算して列挙したものを消去する。
3. 以下繰り返し、マークされた多項式が既約多項式、消去された多項式が可約多項式である。

1	10	11	100	101	110	111	1000
1001	1010	1011	1100	1101	1110	1111	10000
10001	10010	10011	10100	10101	10110	10111	11000
11001	11010	11011	11100	11101	11110	11111	100000

この表からF₂[x]において、x,x+1,x²+x+1,x³+x+1,x³+x²+1、x⁴+x+1,x⁴+x³+1、x⁴+x³+x²+x+1、…が既約多項式と分かった。

F₃[x]におけるアルゴリズム

1. 初めに1,2をマークする。xにマークし、xとx以上の多項式を掛け算して列挙したものを消去。
2. 残った多項式で最小のx+1にマークし、x+1とx+1以上の残った多項式を掛け算して列挙したものを消去。
3. 以下繰り返し、残った物のうち係数が全て2の物を消去する。最後に残った多項式が既約多項式。

1	2	10	11	12	20	21	22	100
101	102	110	111	112	120	121	122	200
201	202	210	211	212	220	221	222	1000
1001	1002	1010	1011	1012	1020	1021	1022	1100
1101	1102	1110	1111	1112	1120	1121	1122	1200
1201	1202	1210	1211	1212	1220	1221	1222	2000
2001	2002	2010	2011	2012	2020	2021	2022	2100
2101	2102	2110	2111	2112	2120	2121	2122	2200
2201	2202	2210	2211	2212	2220	2221	2222	10000

この表から、F₃[x]においてx,x+1,x+2,2x+1,x²+1,x²+x+2,x²+2x+2,…が既約多項式と分かった。

係数の関係から、例えばx²+2x+2と2x²+x+1は同じ多項式（同値類）を表していることがわかる。

自然数の場合と同じように、n番目までの既約多項式を求めればn²番目までの既約多項式が漏れなく列挙できる。具体的にはn次多項式で判定が終われば2n次多項式までの既約多項式が得られる。

欠点も大体同じで、時間がかかること、次数のおおきな多項式が既約かどうか調べたい時でも1次の多項式から調べないと列挙漏れが出てしまうこと、表の拡張がしにくいことが挙げられる。また、あらゆる素数pでF_p上可約だがZ上既約という多項式も存在するので万能ではないという事もある。

論理的背景

これは環論における一意分解整域の素イデアルを生成元の小さなイデアルから列挙するアルゴリズムである。元をうまく並べることができれば、上記の例のように他の環に対しても流用することができる。自然数は環ではないが整数に拡張すれば一貫性が保たれる。

例えば、F₃[x]のアルゴリズムは多項式環F₃[x]の素イデアル(f(x))を列挙する作業に相当する。最初に単元{1,2}を排除し、最後に途中まで素イデアルと同じ振る舞いをする、素数から生成されたイデアル(2,f(x))を排除して既約多項式の定数倍を除いている。

既約多項式は多項式環において素数のような役割を持つため、しばしば既約であるかどうかが問題になるが、一般に多項式の既約判定は難しい。しかし、既約判定の一つとして有限体係数に限定して判定する方法があり、F_p[x]で既約→Z[x]で既約→Q[x]で既約、が一般に成り立つ。有理係数を定数倍して整数にし、適当な素数で合同をとることでQ[x]をF_p[x]で判断する事が可能な場合がある。係数をF_p[x]に限定するのは、Z[x]だと1次式の時点で無限個あり作業が終わらないためである。

F₂[x]でx²+x+1が既約と分かったが、係数を2で割ったあまりが同じになる多項式、x²+3x+1, x²+x+3, x²+3x+3、…あるいはF₃[x]でx²+2x+2は既約だったが、係数を3で割ってと同じになるx²+2x+5, x²+5x+2、…などもZ[x]、ひいてはQ[x]において既約多項式である。F₂[x]においてx³+x²+1が既約であると知っていれば、3x³+27x²+14x+7が既約多項式であるとすぐに判別できるのである。

関連項目

• 数学
• アルゴリズム
• 数学関連用語の一覧
• 素数
• ガウス整数
• 多項式
• 環(数学)
• 体(数学)