テキストの書籍化なのでわかりやすい！
「１章 総合問題」(30ページ)に、
という、素数判定の課題があった。
素数（prime number）とは、
で、インターネットを安全かつ安心して利用するための暗号化技術にも使われていて、
ＡＩとまったく無縁とはいえない概念だ。
具体的には、
「ＲＳＡ」という公開鍵暗号方式で使われる暗号アルゴリズムが有名で、
『数学の言葉で世界を見たら』では、
面白いし有意義だが少し難しい（数式あり）
「フェルマーの小定理」から「オイラーの定理」を応用するところまで解説してあり、
ありがたいが、こんな数式を見ていては先に進めない。
とりあえず、
「素数判定」をググると、
いちばん基本的な方法が、
「エラトステネスのふるい法(試し割り法)」
だとわかった。
たとえば、
１〜１００までの自然数の中から素数を見つけようとすると、
まず、数字を書き出し(１、１００は素数ではないので省略)、
なんか昔やったような記憶がある
２を残して、２に２、３、４を掛けた倍数を順番に消していく。
縦にスッと消せるので気持ちいい！
次に消されていない数を同様に消していき、
最終的に次のような結果になる(以上『数学の言葉で世界を見たら』より)。
まるをつけたのが素数。
そして、コードを書くために、
「エラトステネスのふるい法」の手順をまとめたものがこちら(Wikipediaより)。
２．探索リストの先頭の数を素数リストに移動し、その倍数を探索リストからふるい落とす。
３．上記のふるい落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
４．探索リストに残った数を素数リストに移動して処理終了。
ここで疑問なのは、
３．の「xの平方根に達するまで行う」
というところ。
これもググって、理解した。
下記サイトの写メ ©️@srtk86
このサイトを参照した。
でも、ここまで来ても、
いきなりコードは書けないので、
「１０までの素数を表示するプログラム」を見てみた。
簡単そうでもなかなか書けない。
さっきの｢平方根まで云々｣のところが
int(10 ** 0.5) + 1
なのだが、すこし “？” だったので、
いろいろ調べて、すっきりさせた。
import math
で、Python のmath モジュールをインポートして、
math.ceil(math.sqrt(10))
としたのだ。
そして、できた解答がこちら。
まあ、さっきのコードの10をNに直しただけだけど
ああ、ここまで来るのに３日もかかった。
このコード、まだまだ改善の余地はある。
でも、これって実はSymPyのライブラリを使えば一発なのだ。
たった２行のコード書くだけ（泣）
まあ、ライブラリ使ってしまえば勉強にはならないんだけれど。
Follow me!
