エラトステネスのふるい
用語
Sieve of Eratosthenes

エラトステネスのふるい

一定範囲の自然数を並べ、最小の素数から順にその倍数をふるい落としていくことで、素数だけを効率よく見つける方法。
ひとことで言うと

素数を効率よく見つけるための、古代から伝わる計算法。

エラトステネスのふるいとは

この用語の要点
  • 古代ギリシアの学者エラトステネスが考案したとされる、素数を見つけるためのシンプルで効率的な方法
    • 数を並べて、小さい素数から順にその倍数を消していく
    • 消し終わって残った数が、その範囲の素数

素数とは、1より大きい自然数のうち、1と自分自身以外に約数を持たない数のことです(※『素数』参照)素数1より大きい自然数のうち、1と自分自身以外に約数を持たない数。詳しく見る →。

エラトステネスのふるいは、一定範囲の自然数を並べ、最小の素数から順にその倍数をふるい落としていく方法です。そうすると、素数だけが残ります。

50までの素数を見つけてみる

1から50までの数を書き、1から順に素数でないものを消していきます。1は素数ではないので消します。次の2は消されていないので素数であり、これは残して、2の倍数(4, 6, 8, …50)をすべて消します。次に消されずに残っている3に出会ったら、これも素数として残し、3の倍数をすべて消します。5、7も同じように進めます。

1から50までの数を並べ、1と、2・3・5・7の倍数を消したあとの表。残った15個が50以下の素数。

この操作を続けると、

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

という数だけが消されずに残り、これが50以下の素数のすべてです。50までなら、2・3・5・7の4つでふるうだけで終わります。

実用的な価値と現代における意義

エラトステネスのふるいは、素数を見つけるための厳密な"論証"というより、手続き(アルゴリズムアルゴリズムある問題を解くための、明確に定められた手順。9世紀の数学者フワーリズミーの名がラテン語化され、算術の計算法を指す語を経てこの言葉になった。)です。単に素数を見つけるだけで、素数に対する新たな性質が明らかになるわけではありません。

しかしコンピューターが発明される前、素数の研究者にとってこのふるいはとても重宝されました。大きな素数表というデータが必要だったからです。

素数の研究そのものは長い間「役に立たない理論」と見なされていましたが、20世紀に入りコンピュータが発展すると、素数は情報セキュリティ(暗号技術)の根幹を支える存在となり、状況は一変しました。

さらに深掘り

名前の由来となったエラトステネスとは

エラトステネスエラトステネス地球の大きさを測った!?大図書館の館長詳しく見る →は、紀元前3世紀の古代ギリシアの天文学者・地理学者で、エジプト・アレクサンドリアにあった大図書館の館長を務めました。

大図書館の資料を自由に読める立場にあり、当時の一流の学者アルキメデスアルキメデス22/7 の秘密!発見と創造の数学者・物理学者詳しく見る →から手紙をもらうほど交流もありました。地球の周長を測定しようとした人物としても知られています。

この名前は本当にエラトステネスのものか

「エラトステネスのふるい」という名前が、本当にエラトステネス自身の発明を指しているのかは、実ははっきりしません。

エラトステネスは詩人・音楽家・文学批評家としても知られる多才な人物で、数学や天文学の業績も多く残しています。ただ、同時代の学者からはギリシア文字の2番目"ベータ"にちなみ「二番手」というあだ名で呼ばれていたという逸話も伝わっています。

日々ひたすら素数を扱う"素数オタク"でなければなかなか思いつかないようなこのアルゴリズムを、これほど幅広い分野を手がけた人物が独力で編み出したと考えるのは、必ずしも自然ではありません。後世の誰かが、権威ある大図書館長エラトステネスの名前をこのアルゴリズムに結びつけただけ、という可能性も十分に考えられます。

ポゥじい
名前の由来をそのまま鵜呑みにせず、「本当にその人の発明なのか」と一歩立ち止まって考えてみる。数学史を読み解くうえでは、これがなかなか大切な視点なんじゃよ。そうやって疑問を持って調べていくと、その人物の人となりや、当時の学問の様子まで見えてくる。ひとつの名前が、時代への入り口になるのじゃ。
ポゥじい博士の見立て

そもそも、エラトステネスが数学で名を残した仕事は、このふるいくらいのものじゃ。しかも、これは素数について何か新しい性質を明らかにしたわけではない。ただの手続き(アルゴリズム)にすぎん。

なぜ彼が突然こんなものを思いついたのか、わしにはどうも判然としない。もしかすると、この逸話自体、18世紀から20世紀ごろに作られた話ではないか、そんな疑いすら持っておる。

それに、いまのコンピューターにとって、この「ふるい」はほとんど役に立たん。素数そのものは、暗号技術の要として花形になった。じゃが、そこで使われるのは何百桁もの素数でな。小さい数から順に倍数を消していくこのやり方では、とても手が届かんのじゃ。素数の出世に、ふるいの方は付いていけなかったというわけじゃな。

本ではこう語られています

エラトステネスのふるいで消されていくのは、まさにこの「長方形に並べられる数」=合成数です。

古代ギリシアの数1 数学はこうして生まれたこの本を見る
ポゥじい
一方で、どのように並べても長方形が作れない数がある。つまり、1列に並べるしかない、つまり「分けられない」数 ―― それが素数じゃ。たとえば2、3、5などがそうじゃな。

合成数・素数・偶数・奇数など、数がどう仕分けられていったのかをじっくり知りたい方には、電子書籍:古代ギリシアの数1 数学はこうして生まれた がおすすめです。小石を並べて数の性質を見つけていく古代ギリシアの考え方を、はじめから順に解説しています。

広告
広告250×250
古代ギリシアの数1 数学はこうして生まれた
電子書籍

古代ギリシアの数1 数学はこうして生まれた

ふるいが消していく「長方形に並べられる数」と、消されずに残る素数。古代ギリシア人が小石を並べて数の性質を見つけていく過程を、対話形式でたどります。

この本を見る