前回の記事では、素数のおもしろさを紹介しました。今回は、実際にパソコンで素数を探してみます。
使うのは、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のオンライン個別指導をひらいています。数学の「なぜ」を一緒に考えるのが好きな方は、この記事の下の「おすすめのサービス」からのぞいてみてください。