数学 スキル
学びになった 0 保存 0

パソコンで素数を探してみよう。インストール不要、1行のコードから始める数学×プログラミング

パソコンで素数を探してみよう。インストール不要、1行のコードから始める数学×プログラミング

前回の記事では、素数のおもしろさを紹介しました。今回は、実際にパソコンで素数を探してみます。

使うのは、Pythonというプログラミング言語です。むずかしそうに聞こえるかもしれませんが、この記事で書くコードはどれも1行だけです。プログラミングをしたことがない方でも大丈夫です。

私はシステムエンジニアとして働きながら、大学院で素数を研究していました。数学とプログラミングは、思っている以上に相性のよい組み合わせです。

準備:ブラウザだけで始められる

インストールは必要ありません。「Google Colaboratory」(グーグル・コラボラトリー)という、ブラウザで使える無料のPython環境を使います。

1. 「Google Colaboratory」で検索して開く(Googleアカウントでログイン)

2. 「ノートブックを新規作成」を押す

3. 出てきた入力欄(セル)にコードを貼りつけて、左の ▶ ボタンを押す

これだけで、コードが動きます。

ステップ1:91を割り切る数を探す

前回の記事で「91は素数に見えるけれど、7 × 13 だ」という話をしました。これをパソコンに確かめてもらいます。

n = 91; print([d for d in range(2, n) if n % d == 0])

結果は [7, 13] と出ます。

読み方はこうです。「2からn−1までの数 d のうち、n を d で割ったあまり(n % d)が 0 になるものを、すべて並べて表示する」。割り切る数が1つも出てこなければ、その数は素数です。

ステップ2:1から100までの素数をすべて出す

print([n for n in range(2, 101) if all(n % d != 0 for d in range(2, n))])

2、3、5、7……97まで、25個の素数が表示されます。前回の記事の表と同じです。

「all(……)」は「すべての d について、割ったあまりが 0 でない」、つまり「どの数でも割り切れない」という意味です。素数の定義を、そのままコードにしただけです。

ステップ3:数学の力でプログラムを速くする

ここからが、数学とプログラミングがつながるところです。

ステップ2のコードは、たとえば97が素数かどうかを調べるのに、2から96まで全部で割っています。でも、本当はそんなに調べる必要はありません。

素数プログラム_ルートの図

36を割り切る数を並べると、1 × 36、2 × 18、3 × 12、4 × 9、6 × 6 と、6をはさんでペアになっています。6は36の平方根(√36)です。

ペアの片方は必ず6以下にいるので、6以下の数で割り切れなければ、それより大きい数でも割り切れません。つまり、n が素数かどうかは、√n までの数で割ってみれば十分なのです。97なら、√97 は約9.8なので、2から9まで調べれば終わりです。

これをコードにすると、こうなります。

print(len([n for n in range(2, 100001) if all(n % d != 0 for d in range(2, int(n ** 0.5) + 1))]))

「n ** 0.5」が √n です。結果は 9592。10万までに素数は9592個あることが、一瞬でわかります。

このくふうがないと、同じ計算に何倍も時間がかかります。数学を知っていると、プログラムが速くなる。これが、私が数学とプログラミングを一緒に学ぶことをすすめる理由です。

ステップ4:素数はだんだんまばらになる

最後のコードの「100001」を変えると、いろいろな範囲の素数を数えられます。結果をまとめると、こうなります。

・100まで:25個(100個のうち25%)

・1000まで:168個(16.8%)

・1万まで:1229個(約12.3%)

・10万まで:9592個(約9.6%)

数が大きくなるほど、素数の割合は少しずつ減っていきます。ただ、そのへり方にはきちんとした法則があることがわかっていて、「素数定理」と呼ばれています。でたらめに見える素数の並びにも、遠くから見ると形がある。このふしぎさが、素数の研究の入り口です。

ステップ5:前回の記事の話を確かめる

双子素数を探す

primes = [n for n in range(2, 101) if all(n % d != 0 for d in range(2, n))]; print([(p, p + 2) for p in primes if p + 2 in primes])

100までの双子素数(差が2の素数のペア)が、(3, 5) から (71, 73) まで8組表示されます。

30031を割り切る数を探す

print([d for d in range(2, 30031) if 30031 % d == 0])

結果は [59, 509]。前回の記事で紹介した「2 × 3 × 5 × 7 × 11 × 13 + 1 は素数ではない」ことが、自分の手で確かめられました。

やってみましょう

1. ステップ1のコードの 91 を 221 に変えると、何が出てくるでしょう?

2. ステップ3のコードを使って、1000までの素数の個数を確かめてみましょう

3. ステップ5の双子素数のコードの 101 を 1001 に変えると、1000までに双子素数は何組あるでしょう?

答え

1. [13, 17]。221 = 13 × 17 で、素数ではありません

2. 168個(コードの 100001 を 1001 に変える)

3. 35組(ステップ5のコードの print(……) を print(len(……)) に変えると、組の数が表示されます)

まとめ

・Google Colaboratoryを使えば、インストールなしでPythonが動く

・素数の定義は、そのまま1行のコードにできる

・「√n まで調べれば十分」という数学の知識で、プログラムが速くなる

・プログラムを使うと、数学の話を自分の手で確かめられる

ストアカでは、算数から大学の数学まで、1対1のオンライン個別指導をひらいています。数学の「なぜ」を一緒に考えるのが好きな方は、この記事の下の「おすすめのサービス」からのぞいてみてください。

この記事を読んだ方におすすめ

この記事を書いた先生の講座・サービスです。先生から直接学べます。

この記事を書いた先生
須田 貴之 シルバーバッジ
絶対に怒らない元教員小中高の算数数学&大人のSPI
フォロワー 0 記事 28 受講者 25

はじめまして、須田貴之と申します。元小学校教員で、現在は算数・数学の個人指導をしています。 小学生の算数から、中学・高校の数学、大学レベルの内容まで、幅広くお教えできます。大学院では楕円曲線という分野を専門的に学び、数学の面白さと難しさの両方を、身をもって知ってきました。 私…

須田 貴之