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