---
tags: 數學
title: 篩法
---

:::info
### 題目放這兒：
- [線性篩模板題](https://www.luogu.com.cn/problem/P3383)
- [線性篩練習題](https://loj.ac/p/6165)
- [埃氏篩 ZJ a505](https://zerojudge.tw/ShowProblem?problemid=a505)
:::
:::success
## 暴力篩法
- 如果要找出1~n裡面所有質數，你會怎麼做？
- 粉直覺的想到一個個判斷是否為質數，對吧！
- 暴力判斷質數的話，複雜度$O(n\times\sqrt{n})$
- 使用先進一點點的費瑪質數判定或是Miller-Rabin方法，複雜度$O(n\times logn)$
:::
:::success

## 埃氏篩法
- 如果我們確定 p 是質數，我們就把 p 的倍數一個個全部篩掉就好拉～
- 複雜度：$O(n\times ln(ln(n)))$
- 複雜度怎麼長這樣的別問我我也不知道:-(

:::
:::success

## 線性（歐拉）篩法
- 埃氏篩的優化
- 在埃氏篩裡，一個合數可能被多個質數篩掉，而我希望只被一個最小的質因數篩掉
- 第9行code是精隨！！
- 複雜度：$O(n)$

### 模板code如下（不保證正確）：

bool isprime[];
vector<int> primes;
void euler_seive(int n){
    memset(isprime, 1, sizeof(isprime));
    for(int i = 2; i <= n; ++i){
        if(isprime[i])primes.emplace_back(i);
        for(int j = 0; j < primes.size() && i * primes[j] <= n; ++j){
            isprime[i * primes[j]] = false;
            if(i % primes[j] == 0)break;
        }
    }
}

:::