演習課題「エラトステネスの篩を実装する」
右側のコードエリアには、関数eratosthenesを用いて1以上1,000以下の全ての整数について素数判定をおこなうコードが用意されています。関数eratosthenesのコードを書き加え、コードを完成させてください。
期待する出力値
なし
＃03:エラトステネスの篩
このチャプターでは、ある整数以下のすべての素数を見つけるアルゴリズムである「エラトステネスの篩」について学習します。
isPrimeを計算するときのiのループ範囲は、実は√nまでで十分です。import math
isPrime = [True] * (n+1)
isPrime[0], isPrime[1] = False, False
for i in range(2, int(math.sqrt(n))+1):
if not isPrime[i]:
continue
for j in range(i*2, n+1, i):
isPrime[j] = False
return isPrime
def eratosthenes(n):
isPrime = [True] * (n+1)
isPrime[0], isPrime[1] = False, False
for i in range(2, n+1):
if not isPrime[i]:
continue
for j in range(i*2, n+1, i):
isPrime[j] = False
return isPrime
n = 813
isPrime = eratosthenes(n)
for i in range(1, n+1):
if isPrime[i]:
print(f"{i} は素数")
else:
print(f"{i} は素数ではない")