エラトステネスの篩

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

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

概要

エラトステネスとは紀元前3世紀頃の学者であり、地球の大きさを誤差数%以内で推定した事などで有名な人物である。エラトステネスの篩はそんな彼の名に由来し、古くは、1世紀～2世紀の数学者ニコマコスの著作「算術入門」において数回言及されている。例えば第13章で「これらの数の算出法はエラトステネスによって篩と呼ばれた、なぜなら……」などと記載がある^[1]。（ただし「エラトステネスが考案した」と明言する記載ではないようだ？）

素朴ながらも確実にすべての素数を求めることができる、優秀なアルゴリズムである。合成数が次々に消去され、素数が残っていく様が「ふるいにかける」ようであるからこの名前がついた。

以下がそのアルゴリズムの概略である。

自然数におけるアルゴリズム

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

以上の作業を繰り返すことで素数を求めることができる。以下は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、整数なら1と-1、有理数なら0を除くすべての元である。体は0を除くすべての元が単元になる。

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

1. 0を中心にマス目状にガウス整数を並べ、0と1,-1,i,-iを除外する。1,-1,i,-iは単元。
2. (1+i)の単元倍をマークし、1+iの倍数(1+i)(x+yi)=(x-y)+(x+y)iを消去する。
3. 残った数で0に近い(1+2i)の単元倍をマークしてその倍数(x-2y)+(x+2y)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、…などがガウス素数であることが分かった。aを単元倍した元bを、aに同伴な元bと呼ぶ。例えば±(1+2i)、±(2-i)は互いに同伴なガウス素数である。

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

• 段階2.で2から始めても良いが、次の1±iの倍数の消去の過程で2が消えてしまう。つまり、ガウス整数において2はガウス素数ではないという事がわかる。実際、2=(1+i)(1-i)であり、素因数分解できる。これは自然数の場合に「仮に素数を飛ばしても検算の時にそこからやり直せば問題ない」という事に対応する。
• こちらは0を中心に(2n+1)×(2n+1)マスまで終わっていれば少なくとも中心から半径n²マスまでのガウス素数が求まる。また、消去される倍数が正方形の頂点上に並ぶので各ステップで消去される倍数もキレイなパターンを描く。
• 欠点はやはり時間がかかるところ。途中から表の拡張をするのはかなり難しい。

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

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

整数を素数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の物を消去する。
4. マークされ残った多項式が既約多項式。

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

モニックな多項式（最大次数の係数が1の多項式）に限定した表は以下のとおり。

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,…が既約多項式と分かった。

1,2は単元なので、例えば(x²+2x+2)を2倍した式(2x²+x+1)は同伴な既約多項式である。これはちょうど有理数係数の既約多項式について、定数倍した式を同一の式と見なすことと対応する（有理数は0を除いた全ての数が単元であるため）。

---

• 自然数の場合と同じように、n番目までの既約多項式を求めればn²番目までの既約多項式が漏れなく列挙できる。具体的にはn次多項式まで判定が終われば2n次多項式までの既約多項式が得られる。
• 係数をF_p[x]に限定するのは、Z[x]だと1次式の時点で無限個あり作業が終わらないためである。
• 欠点も大体同じで、時間がかかること、次数のおおきな多項式が既約かどうか調べたい時でも1次の多項式から調べないと列挙漏れが出てしまうこと、表の拡張がしにくいことが挙げられる。また、整数と異なり消去される多項式の法則性が乏しく、実際に計算してみないと既約かどうかすぐにはわからない。

論理的背景

これは環論の言葉でいえば、単項イデアル整域の素イデアルをリストアップするアルゴリズムである。上記の例のように全ての元をうまく並べることができるような環に対して流用することができる。自然数は環ではないが整数に拡張すれば一貫性が保たれる。

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

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が既約多項式であるとすぐに判別できるのである。ただし、あらゆる素数pでF_p上可約だがZ上既約という多項式も存在するので万能ではないという事に注意しなければならない。

リーマンゼータ関数との関係

エラトステネスの篩とは直接関係しないが、参考として記述する。

リーマンゼータ関数ζ(s)とは以下の関数である。

ζ(s)=1/1^s+1/2^s+1/3^s+…=Σ_n1/n^s

この関数は比較的シンプルな形をしているが様々な性質を持ち、数学の深淵に迫る関数の一つとして研究の対象となっている。この関数は素数とも関係しており、和を積に式変形する方法の一つにエラトステネスの篩のようなふるまいを見せるものがある。式変形は以下の通り。

ζ(s)=1+1/2^s+1/3^s+1/4^s+…

1/2^sζ(s)=1/2^s+1/(2^s×2^s)+1/(2^s×3^s)+1/(2^s×4^s)+…

(1-1/2^s)ζ(s)=1+1/3^s+1/5^s+1/7^s＋1/9^s+1/11^s+…

1/3^s(1-1/2^s)ζ(s)=1/3^s+1/(3^s×3^s)+1/(3^s×5^s)+1/(3^s×7^s)+…

(1-1/3^s)(1-1/2^s)ζ(s)=1+1/5^s+1/7^s＋1/11^s+1/13^s+1/17^s+1/19^s+1/23^s+1/25^s+…

1/5^s(1-1/3^s)(1-1/2^s)ζ(s)=1/5^s+1/(5^s×5^s)+1/(5^s×7^s)+…

(1-1/5^s)(1-1/3^s)(1-1/2^s)ζ(s)=1+1/7^s+1/11^s+1/13^s+…

…

…(1-1/11^s)(1-1/7^s)(1-1/5^s)(1-1/3^s)(1-1/2^s)ζ(s)=1

ζ(s)=1/((1-1/2^s)(1-1/3^s)(1-1/5^s)…)=1/(Π_p(1-1/p^s))　（pは素数）

このようにして合成数の項がエラトステネスの篩と同じ順番で次々と消去され、素数の項が左辺に累積していくことがわかる。

関連項目

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

脚注

1. *Internet Archiveに収録されている、Nicomachi Geraseni Pythagorei - Introductionis arithmeticae libri II（Richard Gottfriedによる1866年出版のバージョン）より。