ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


エラトステネスの篩


ヨミ: エラトステネスノフルイ
掲示板をミル!
3カキコ!

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

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


概要


エラトステネスとは紀元前3世紀頃の学者であり、地球の大きさを誤差%以内で推定した事などで有名な人物である。エラトステネスの篩はそんな彼の名に由来し、古くは、1世紀~2世紀の数学ニココスの著作「算術入門」において数回言及されている。例えば第13章で「これらの数の算出法はエラトステネスによって篩と呼ばれた、なぜなら……」などと記載があるInternet Archiveに収録されている、Nicomachi Geraseni Pythagorei - Introductionis arithmeticae libri II(Richard Gottfriedによる1866年出版のバージョン)[外部]より。。(ただし「エラトステネスが考案した」と明言する記載ではないようだ?)

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

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


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


  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,…が素数であることが分かった。


利点



欠点



関連動画



■sm33041015[ニコ動]


関連項目




応用


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

以下、応用例としてガウス整数と多項式、ゼータ関数の式変形について記述する。


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


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

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

  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. マークされた数がガウス素数である。

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


次へ»
最終更新日: 18/09/24 23:53
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ