線性篩法 (不專業講解)

作者：瘋頭是笨蛋│2021-04-27 23:39:23│巴幣：5│人氣：445

寫某cf題，我想要在最快的時間建出

每個數包含哪些質因數

然後我就回去看我很久以前抄別人 C++ 的 code

我一直都搞不太懂線篩原理

於是花了幾秒的時間理解一下
希望我打完這邊能喇出我想要的東西

<鬼之hr分隔線>

一般大家印象中的篩法

是用質數的 n 倍去篩出合數

這樣會有重複篩選的問題

例如 2*15 = 3*10 = 5*6 = 30

但如果這個表示法的特性

每個數就只會被篩到一次而已

先上 python 的線篩 code

from time import time
time1 = time()
N = int(1e5)
is_prime = [True] * (N + 1)  # have 0
is_prime[0] = is_prime[1] = False
prime = []
for n in range(2, N + 1):
    if is_prime[n]:
        prime.append(n)
    for p in prime:
        if p * n > N:  # Index out of range
            break
        is_prime[p * n] = False
        print("%d*%d = %d" % (p, n, p * n))
        if n % p == 0:
            break
print(prime)
print(time() - time1)

以下不專業講解...

首先，對於每個合數 a
則 a 恰有一個唯一的表示法 p * n

且 p 為 a 的最小質因數，以及 p ≤ n

顯然說到最小的質因數肯定是唯一的

這部分理解上應該沒有什麼大問題

我們先無視最後的那個 break

首先先要證明這能正確地篩掉所有合數

由於 ≤ n 的所有質數都會被迭代到

當我們也迭代所有的 n 值

則這就是所有 p ≤ n 的組合

再來要搞清出為什麼那邊可以 break

這個 break 會導致 > 某個 p 的質數不會跟 n 一起篩