東大数学2024問題6 (part 6): データベースとの比較 - 複天一流：どんな手を使ってでも問題解決を図るブログ

前回のあらすじ
The PrimePagesのデータベースとの比較
計算結果

前回のあらすじ

エラトステネスの篩のコードが書き終わった。最初の30個の素数(2,3,....,113)は正確に計算することができたが、果たしてたまたまなのか、それともちゃんと機能しているのか、あらかじめ公開されている正しい素数のデータベースと比較してみたい。

The PrimePagesのデータベースとの比較

The PrimePagesからダウンロードした最初の1万個の素数を（自分で作ったエラトステネスの古いのコードが）再現できるかどうか確認してみる。

データを読み込む部分と、エラトステネスの篩で計算する部分を融合させる。データベースは、10個の素数をまとめて1行で表現しているので、10個ずつinput()関数で読み込み、プログラムが用意した「配列」（Pythonではlistと呼ぶ）に収納していく形を採用する。

Nt = 10000
Nx = 10
Ny = Nt/Nx

prime_data = [ [0 for i in range(Nx)] for j in range(Ny)]

初期値は0とした。ネストの最も内側にあるデータが連続配置されており、アクセスするには

np = int(prime_data[j][i])

とする。連続した部分は、右側の添字で制御するという形式である。

npの位置にあるprime_tableの値の真偽を調べ、もし真であればnpは正しく計算されデータベースと同じ結果になっていることになる。

print(prime_table[np])

もちろん、npが素数でない場合も検査する必要がある。その場合にはFalseが出ればOKである。

ということで、検査部分は次のような感じになった。

ip=0
for nj in range(Ny):
    for ni in range(Nx):
        np = int(prime_data[nj][ni])
        for i in range(ip,np+1):
            if i != np and prime_table[i] == True:
                print(" Error A: ", nj, ni, i, ip, np)
                sys.exit()
            if i == np and prime_table[i] == False:
                print(" Error B: ", nj, ni, i, ip, np)
                sys.exit()
        print(" {0:7d}  {1:7d}".format(np,i), end='')
        ip = np + 1
    print()
print()
print('Success: There is no inconsistency\n')
print("Prime-number search completed.")