ChatGPTに指定した数までの素数をできるだけ高速に出力してもらうプログラムを書いてもらった

Python

ChatGPTに指定した数までの素数をできるだけ高速に出力してもらうプログラムを書いてもらいました。

 

ChatGPTへの指示文:

指定した数までの素数をできるだけ高速に出力するpythonプログラムを書いてください。最後に計算にかかった時間も表示してください。

 

ChatGPTからの回答 

以下は、 指定された数までの素数を高速に出力するPythonプログラムです。このプログラムは、エラトステネスのふるいと呼ばれるアルゴリズムを使用して、素数を見つけます。

import time

def find_primes(n):
    # 2からnまでの数のリストを作成する
    numbers = list(range(2, n+1))

    # エラトステネスのふるいを使用して、素数を見つける
    primes = []
    while len(numbers) > 0:
        prime = numbers[0]
        primes.append(prime)
        numbers = [n for n in numbers if n % prime != 0]

    return primes

# テスト用の入力値
n = 10000

# 素数を探す
start_time = time.time()
primes = find_primes(n)
end_time = time.time()

# 結果を表示する
print(primes)
print("Found", len(primes), "primes.")
print("Time taken:", end_time - start_time, "seconds.")

このプログラムでは、find_primesという関数を定義し、2からnまでの数のリストを作成し、それを最初の素数として取り出します。次に、この素数で割り切れる数をリストから取り除き、残りの数で同じことを繰り返します。このプロセスを繰り返すことで、素数のリストが得られます。 最後に、timeモジュールを使用して、プログラムが実行されるのにかかった時間を測定し、結果を表示します。

 

実行した結果:

下記のようにきちんと動作しました。1万だとあっという間だったので10万にしてみました。

結果は
Found 9592 primes.
Time taken: 3.2111270427703857 seconds.

ということで、3.2秒かかりました。仮想環境なせいもあり、少し遅いですね。


環境:
マシン Ryzen 7 5825U
ホストOS Win11
ゲストOS Virtual Box 7.0.6 / Ubuntu22LTS / Python 3.8.13 / Jupyter notebook 6.4.12

 

追記:

もう少し早く動くものを再度作成してもらいました。結果、0.1秒とかなり早くなりました。

このプログラムでは、limit変数に100000を設定し、最初にすべての数を素数と仮定したsieveリストを作成します。そして、0と1は素数ではないため、sieve[0]とsieve[1]をFalseに設定します。 次に、2からlimitの平方根までのすべての素数について、sieveリストを更新するために、2乗からlimitまでのiの倍数をFalseに設定します。最後に、sieveリストを調べて、Trueのインデックスを素数リストに追加します。


import time

start_time = time.time()

limit = 100000
sieve = [True] * (limit + 1)
sieve[0] = sieve[1] = False

for i in range(2, int(limit ** 0.5) + 1):
    if sieve[i]:
        for j in range(i * i, limit + 1, i):
            sieve[j] = False

primes = [i for i in range(limit + 1) if sieve[i]]

for prime in primes:
    print(prime)
    
end_time = time.time()


print("Found", len(primes), "primes.")
print("Time taken: {:.5f} seconds".format(end_time - start_time))
追記2:

シンプルに「10万までの整数のうち、素数はいくつありますか？」と質問してみました。

回答:

10万までの整数のうち、素数の数を求めるには、素数の定義を利用して、それぞれの数が素数かどうかを判定していく必要があります。 素数とは、1と自分自身以外に正の約数を持たない自然数のことです。1は素数ではないので、2から10万までの数について、素数であるかどうかを判定します。 以下は、Pythonで実装したプログラムです。



def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

count = 0
for i in range(2, 100001):
    if is_prime(i):
        count += 1

print(count)

このプログラムを実行すると、10万までの整数のうち、素数は9592個あることがわかります。