# 歐拉篩法(線性篩)

## 歐拉篩法是什麼?

歐拉篩法是埃式篩 (若不知道埃式篩可以參考這邊：[埃拉托斯特尼篩法](https://hackmd.io/@kesshoban3310/rk5X5VuXs))的一種優化。在歐拉篩法中，每個數在判斷是否為質數時，只需判斷一次就可以知道這個數是否為質數，所以歐拉篩法又稱線性篩。

## 歐拉篩法想法

在歐拉篩法中，**每個合數只被自身最小的質因數篩選過一遍**，例如：
$15=3*5$
$102=2*3*17$
則 $15$ 會被 $3$ 判斷為合數， $102$ 會被 $2$ 判斷為合數

## pseudo code (虛擬碼)

建立一個整數n，將其值設為範圍上限
將is_prime[]中所有元素設為1    # 如果is_prime[n]==1，代表n是質數 
建立一個存質數的primelist    # 將目前已知的所有質數存於primelist中
for i = 2 ~ n :
    if is_prime[i] == 1 :        # 如果is_prime[i]==1，將i加入primelist
        將i加入primelist中
    for j = primelist中的元素 :
        if i * j > n :        # 如果i*j超出範圍，跳出迴圈
            跳出for迴圈
        isprime[i * j] = 0    # 將i*j標記為合數
        if i % j == 0 :
            跳出for迴圈    # 歐拉篩法關鍵：如果i是j的倍數，則i有質因數j，
                          # 且primelist中元素只會越來越大，所以到這裡就
                          # 需停下(因為每個合數只能被自身最小的質因數篩
                          # 選過一遍)