質數表

在求質數的題目中，當測資太大時，很容易就會超時。

這時就可以選擇建表

埃拉托斯特尼篩法

Wiki

程式碼

MAX = 10**6
prime_table = [1] * MAX
prime_table[0] = prime_table[1] = 0

for i in range(2, int(MAX ** 0.5) + 1):
    if prime_table[i]:
        for j in range(i * i, MAX, i):
            prime_table[j] = 0

Contributors

lucashsu95

Changelog

Last edited about 1 month ago

View full history

f9e9350-使用埃拉托斯特尼篩法演算法添加素數表