質數的線性篩法

我們希望每個合數只被篩到一次
可以發現，對於每一個合數$N$
設它的最小質因數為$P$
一定有$\frac{N}{P}\geq P$
而且$P\leq \frac{N}{P}最小的質因數$
因此，我們可以從小到大枚舉$Q$ ($\frac{N}{P}$)
所有$\leq Q最小的質因數$的質數$P$去更新$PQ$
實作上枚舉$P$的時候發現$P$整除$Q$時跳出迴圈即可

code:

#include<cstdio>
#include<vector>
using namespace std;
bool IS_PRIME[65537];
vector<int>PRIMES;
int main()
{
    for(int i=2;i<=65536;i++)IS_PRIME[i]=true;
    for(int n=2;n<=65536;n++)
    {
        if(IS_PRIME[n])PRIMES.push_back(n);
        for(int i=0;i<(int)PRIMES.size()&&PRIMES[i]<=65536/n;i++)
        {
            IS_PRIME[n*PRIMES[i]]=false;
            if(n%PRIMES[i]==0)break;
        }
    }
    for(int i=0;i<(int)PRIMES.size();i++)printf("The %d-st prime is %d.\n",i,PRIMES[i]);
    return 0;
}