素数判定のプログラムを書けといわれて、かれこれ3日(泣)〜キカガク・AIスクールの復習その8

キカガクAIスクール
鶏肉のシャリアピン炒め。上の玉ねぎバターソースが悪魔的美味しさ!

『東京大学のデータサイエンティスト育成講座』

テキストの書籍化なのでわかりやすい!

「1章 総合問題」(30ページ)に、

Nを自然数として、Nまでの素数を表示する関数を書け。

という、素数判定の課題があった。

素数(prime number)とは、

1 より大きい自然数で、正の約数が 1 と自分自身のみであるもの(Wikipedia)

で、インターネットを安全かつ安心して利用するための暗号化技術にも使われていて、
AIとまったく無縁とはいえない概念だ。

具体的には、
「RSA」という公開鍵暗号方式で使われる暗号アルゴリズムが有名で、
『数学の言葉で世界を見たらでは、

面白いし有意義だが少し難しい(数式あり)

「フェルマーの小定理」から「オイラーの定理」を応用するところまで解説してあり、
ありがたいが、こんな数式を見ていては先に進めない。

とりあえず、
「素数判定」をググると、
いちばん基本的な方法が、
「エラトステネスのふるい法(試し割り法)」
だとわかった。

たとえば、
1〜100までの自然数の中から素数を見つけようとすると、
まず、数字を書き出し(1、100は素数ではないので省略)

なんか昔やったような記憶がある

2を残して、2に2、3、4を掛けた倍数を順番に消していく。

縦にスッと消せるので気持ちいい!

次に消されていない数を同様に消していき、
最終的に次のような結果になる(以上『数学の言葉で世界を見たら』より)。

まるをつけたのが素数。

そして、コードを書くために、
「エラトステネスのふるい法」の手順をまとめたものがこちら(Wikipediaより)

1.探索リストに2からxまでの整数を昇順で入れる。
2.探索リストの先頭の数を素数リストに移動し、その倍数を探索リストからふるい落とす。
3.上記のふるい落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
4.探索リストに残った数を素数リストに移動して処理終了。

ここで疑問なのは、
3.の「xの平方根に達するまで行う」
というところ。

これもググって、理解した。

下記サイトの写メ ©️@srtk86

このサイトを参照した。

でも、ここまで来ても、
いきなりコードは書けないので、
「10までの素数を表示するプログラム」を見てみた。

簡単そうでもなかなか書けない。

さっきの「平方根まで云々」のところが

int(10 ** 0.5) + 1

なのだが、すこし “” だったので、
いろいろ調べて、すっきりさせた。

import math

で、Python のmath モジュールをインポートして、

math.ceil(math.sqrt(10))

としたのだ。

そして、できた解答がこちら。

まあ、さっきのコードの10をNに直しただけだけど

ああ、ここまで来るのに3日もかかった。
このコード、まだまだ改善の余地はある。

でも、これって実はSymPyのライブラリを使えば一発なのだ。

たった2行のコード書くだけ(泣)

まあ、ライブラリ使ってしまえば勉強にはならないんだけれど。

Follow me!

PAGE TOP