エラトステネスの篩(Python)
(num_theory/prime_sieve.py)

• View this file on GitHub
• Last update: 2024-01-27 17:23:24+09:00

概要

エラトステネスの篩を行い、N以下の数が素数かどうかを格納したリストを返します。（ここら辺の説明については拡充予定）
余りにNが大きすぎるとメモリエラーが出るので注意。

計算量

Verify問題

• アルゴ式：https://algo-method.com/submissions/1147166

Code

# エラトステネスの篩
# Nまでの素数を列挙する
def prime_sieve(N):
    
    # Nまでの数列を作成。Trueならその数字は素数。
    num = [True]*(N+1)
    
    # 0,1は素数でないので1にしておく
    num[0] = False
    num[1] = False
    # 1～Nまでの範囲を走査。
    # 1-indexで考える (ex:1はnum[1],77はnum[77])
    for i in range(2,N+1):
        if num[i]:
            # iが素数である場合、iの倍数のフラグを全て1に変更する
            for j in range(2*i, N+1, i):
                num[j] = False
    return num

N   = int(input())
num = prime_sieve(N+2)

ans = sum(num[:N+1])
print(ans)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.1/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.1/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page