埃筛，线性筛(欧拉筛)

      我们知道在求素数时，普通的暴力通常无法满足许多OJ网站的时间复杂度要求，那么自然需要优化，我们求素数时，不妨把不是素数的先标记，剩下的自然就都是素数（直接暴力这里就不写了）。

埃塞：         

#include<bits/stdc++.h> using namespace std; #define ll long long int prime[20000]; int len; int main() { int n; cin>>n; int book[20000]; memset(book,0,sizeof(book)); for(register int i=2;i<=n;i++) { if(!book[i]) { prime[len++] = i; for(register int j=2*i;j<=n;j+=i) {//每次把这个数的倍数标记 book[j] = 1; } } } /*for(register int i=0;i<len;i++) { cout<<prime[i]<<endl; }*/ }

   埃筛其实还是有一些重复：许多数被重复标记，比如：10既被2标记过，又被5标记过

接下来是线性筛：线性筛的优化主要在于每个数只被筛过一次

#include<bits/stdc++.h> using namespace std; #define ll long long int prime[20000]; int len; int main() { int n; cin>>n; int book[20000]; memset(book,0,sizeof(book)); for(register int i=2;i<=n;i++) { if(!book[i]) { prime[len++] = i; } for(register int j=0;j<len;j++) { if(i*prime[j]>n) break; book[i*prime[j]] = 1; if(i%prime[j]==0)//使每个合数只被它的最小质因数标记 break; } } /*for(register int i=0;i<len;i++) { cout<<prime[i]<<endl; }*/ }