# 質數篩

> 埃拉托斯特尼篩法

* 從小到大，把沒被標記的數中所有的倍數都標記為非質數，而當讀到的數已被標記就跳過

:::success
ex : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
:::

1. **1非質數也非合數，直接畫掉**
~~1~~ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

2. **2沒被畫掉，是質數，把2的倍數全都劃掉**
~~1~~ 2 3 ~~4~~ 5 ~~6~~ 7 ~~8~~ 9 ~~10~~ 11 ~~12~~ 13 ~~14~~ 15 ~~16~~

4. **3沒被畫掉，是質數，把3的倍數全都劃掉**
~~1~~ 2 3 ~~4~~ 5 ~~6~~ 7 ~~8~~ ~~9~~ ~~10~~ 11 ~~12~~ 13 ~~14~~ ~~15~~ ~~16~~

5. **4被劃掉，跳過**

6. **重複動作直到全部走完**

程式碼：

memset(isprime, 0, sizeof(isprime));
isprime[1]=1;
for(int i=2;i<=100000000;++i){
    if(!isprime[i])
        for(int j=2;i*j<=100000000;++j)
            isprime[i*j]=1;
}

質因數分解

ll prime[200010];
//...

vector<ll> pp;
prime[1]=1;
rep(i,2,200005){
    if(!prime[i]) prime[i]=i, pp.pb(i);
    for(auto j:pp){
        if(i*j>200005) break;
        prime[i*j]=j;
    }
}
// pp為質數表

//分解
map<ll,ll> save;
while(n!=1){
    save[prime[n]]++;
    n/=prime[n];
}