前回のあらすじ
前回の記事では、東大2024数学入試問題6を解き始めた。この問題では素数を扱うため、素数データベースを利用して問題探究を数値的に行うことにした。pythonでデータファイルを読み込む方法を知らなかったので、今回は配列に似た概念を用いてそれを実装する計画である。
二次元の配列に似たもの
どうやら、pythonでは「配列」という用語は使わないようである。代わりに「リスト」という概念を採用している。今回利用するのは、CやFORTRANでいう「2次元配列」なのであるが、pythonでは「ネストされたリスト」というらしい。面倒臭いので、pythonでも「二次元配列」と言い続けることにする。
The PrimePagesからダウンロードした素数のデータファイルは、1000行の素数データを含み、1行中には10個の素数が書かれている。プログラム中では、n行目の素数データ列にあるm番目の素数のことをprime_data[n][m]と表すことにする。ただし、n,mは0から数え始めることにする。このような「二次元配列」（つまりネストされたリスト）は、プログラムの先頭で次のように宣言して、メモリを確保することになっているらしい。
prime_data = [ [0.0 for n in range(10)] for m in range(1000)]
括弧の置き方を見ると「ネスト」状になっているから、これを「ネストされたリスト」と呼ぶのであろう。0.0という数値は初期値である。メモリでの連続性を確かめると、nについて連続になっていることがわかる。これは後で確かめてみることにする。
コードを書く
さっそくコードを書いてみた。
Nx = 10 Ny = 1000 prime_data = [[0.0 for i in range(Nx)] for j in range(Ny)] icount = 0 while True: prime_dummy = input().split() if len(prime_dummy) == Nx: prime_data[icount] = prime_dummy icount += 1 if len(prime_dummy) == 1 and prime_dummy[0] == "end.": break
2つのif文は、素数のデータファイルの冒頭と終わりにある、説明書きなどを読み飛ばしたり、ファイルの終わり(EOF)を検知するための処理である。自分でデータファイルを修正してこれらの部分を消去してしまえば、このような条件文は不要となるであろうが、try-except EOFError構文をはめ込む必要が出てきて、結局は同じ手間がかかることになってしまうだろう。
1行ずつ一時的な変数prime_dummyに読み込んで、それを配列に収めていく形式である。読み込みが終わった後も、prime_data[n][m]の形式でアクセスすることができる。
これで、エラトステネスの篩を自分で実装した場合のチェック用データをプログラムに組み込む準備ができた。
次回はエラトステネスの篩のアルゴリズムを見てみたい。このアルゴリズムは有名なもので、当然ながら古代ギリシア時代から知られる有名なものであり、高校数学の教科書でも紹介されている。しかし、現代の暗号資産や電子マネーの照合で利用される巨大な素数を計算するには不向きなアルゴリズムであることも知られている。どんな利点と問題があるのか、調べてみたいと思う。
