19/05/20 19:09:21.17 CAP_USER9.net
ジョジョ・プッチ神父でお馴染みのアレ―“落ち着いて素数を数えたいとき”に便利な「素数を漏れなくリストアップできる方法」が紀元前の数学者に発見されてた件
2019年5月20日 (月) 11:30
素数。それは、自然数のうち自身と1でしか割り切ることのできない数のこと。素数は出現する際の法則性の無さから、はるか昔から数学者たちを悩ませてきました。
例えば素数を書き出してみると……
"
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47……
"
いきなり偶数の2ではじまったかと思えば、3,5,7と奇数が続きます。次の奇数は9ですが、9は3で割り切れてしまうため素数ではありません。1～10までと、10～20まで間の素数は4つなのに、20～30までの間の素数は2つしかありません。
このように素数の出現には一見法則性があるようですが、全貌は明らかになっていません。大きな数字になれば、それが素数か確かめること（素因数分解）は困難になるため、現代ではその性質が暗号理論にも用いられています。
URLﾘﾝｸ(originalnews.nico)
※「素数を数えると安心する」という変わった癖の持ち主・プッチ神父が登場する『ジョジョの奇妙な冒険第六部』（画像はAmazonより）。素数は暗号理論以外に、精神安定にも役立つ!?
ところで、みなさんはそんな素数を、複雑な数式を使わなくても、直感的にリストアップすることができる方法を御存知でしょうか？ 本記事ではredoさんがniconicoに投稿した動画「素数アニメーション Part １」より「エラトステネスの篩（ふるい）」という方法をご紹介します。
URLﾘﾝｸ(originalnews.nico)
まず1周が「2」の棒を想像してください。そこに1から順に数字を巻き付けていきます。すると、こんな感じになります。
URLﾘﾝｸ(originalnews.nico)
URLﾘﾝｸ(originalnews.nico)
数を次々に棒に記入したところで「2の下に並ぶ数を塗りつぶし」ます。すると、「2の倍数」を塗りつぶしたことになります。2の倍数は2で割り切れるので当然、素数ではありません。つまり塗りつぶしたところは素数ではないことがわかる、という仕組みです。
URLﾘﾝｸ(originalnews.nico)
次に、この塗りつぶした数の列を「1周が3の棒」に巻き直してみます。画面に映っている範囲では「6」「8」は2の倍数なのですでに塗りつぶされていますね。
URLﾘﾝｸ(originalnews.nico)
こうして、「1周が3の棒」にどんどん巻き付けていくと、こんな感じになります。そして、塗りつぶされていない3の下に並んでいる数を塗りつぶします。これで「3の倍数」が塗りつぶされました。3の倍数は3で割り切れるので、これまた当然素数ではありませんね。
URLﾘﾝｸ(originalnews.nico)
3の次の4は「1周が2の棒」の時点ですでに塗りつぶされています。一応、「1周が4の棒」に数の列を巻き直してみます。次に巻きつける棒は「1周3の棒」の次ですから「1周が4の棒」です。
URLﾘﾝｸ(originalnews.nico)
そろそろ、この方法に気づいてきた読者の方もいらっしゃると思いますが、次はこの数の列を「1周が5の棒」に巻き付けます。これまでと同様、どんどん巻き付けていきます。
URLﾘﾝｸ(originalnews.nico)
URLﾘﾝｸ(originalnews.nico)
またまた、5の下に並んでいる数を塗りつぶします。これで「5の倍数」が塗りつぶされました。5の倍数は5で割り切れるので、これまた当然素数ではありませんね。
さて「1周が5の棒」の次は……そう「1周が6の棒」、ここは数学らしく「六角柱」と言いましょうか。6は「一周が2の棒」の時点で塗りつぶされています。そして6の下に並んでいる6の倍数もすでに塗りつぶされています。
URLﾘﾝｸ(originalnews.nico)
URLﾘﾝｸ(originalnews.nico)
↓