1.一般的篩法
根據素數定義，對于一個數n,隻要2到sqrt(n）的數無法被n整除即可。相信大家都學過，直接上代碼了。
代碼：
/*
簡單素數輸出：輸入一個大于0的整數n，輸出1到n之間（不包括該整數）的所有素數，
空格隔開（最後一個素數後不輸出空格）
Project:prime
Date: 2019/02/28
Author: Frank Yu
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<stack>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
#define F(i,m,n) for(int i=m;i<n;i++)
//素數判斷
bool JudgePrime(int n)
{
int sqrtn = (int)sqrt(n) + 1;
F(j, 2, sqrtn)//判斷2到sqrtn之間的數能否被n整除
if (n%j == 0)
{
return false;
}
return true;
}
//主函數
int main()
{
int n,sqrti;
bool output = false;//控制空格
scanf("%d",&n);
F(i, 2, n)
{
if (JudgePrime(i))//是素數，則輸出
{
if (output)
{
printf(" %d", i);
}
else
{
printf("%d", i);
output = true;
}
}
}
printf("\n");
return 0;
} 優化：
看下面部分代碼：
int sqrtn = (int)sqrt(n) + 1;
F(j, 2, sqrtn)//判斷2到sqrtn之間的數能否被n整除
sqrtn并不是多此一舉，sqrt(n)是函數，如果寫在for循環裡面,for循環每次都會判斷j是否小于sqrt(n),這樣的話sqrt函數就會運作多次，但n比較大時，會浪費時間。同樣，還有周遊string s時，不要把i<s.length()寫在for循環裡面。
2.埃氏篩法
時間複雜度：O(n*lglgn)
核心思想：
對于已找到的素數，将它的倍數标記為非素數。
/*
2013版 王道機試P92 素數篩法
素數輸出：輸入一個大于0的整數n，輸出1到n之間（不包括該整數）的所有素數，
空格隔開（最後一個素數後不輸出空格）
優化的bug:
n*n不超int即可，否則需要将for (int k = j*j;k < max;k+=j)的j*j改為j*2等，使k的指派不
超過int，當然,你可以讓k是其他類型，不過，數大時，埃氏篩法時間複雜度已經不行了
Project:prime_ai
Date: 2019/02/28
Author: Frank Yu
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<stack>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
#define F(i,m,n) for(int i=m;i<n;i++)
#define max 100001
int prime[max];//儲存篩得的素數
bool mark[max];//标記該數是否已被标記為非素數 true表示非素數
int primesize;
//素數篩法
void init(int n)
{
F(i, 0, n) //初始化
{
mark[i] = false;
}
memset(prime,0,sizeof(prime));
primesize = 0;
F(j,2,n)
{
if (mark[j])continue; //已标記為非素數，跳過
prime[primesize++] = j;//儲存素數
for (int k = j*j;k < n;k+=j)//标記素數所有倍數為非素數
{
mark[k] = true;
}
}
}
//主函數
int main()
{
int n;
bool output = false;
scanf("%d",&n);
init(n);
F(i,0, primesize)
{
if (prime[i] < n)
{
if(output)
{
printf(" %d",prime[i]);//輸出空格
}
else
{
printf("%d",prime[i]);
output = true;
}
}
else break;
}
printf("\n");
return 0;
} 标記素數的倍數時,沒有從j*2開始，從j*j開始，如果從j*m（m<j）開始，求得m的某個素因子時已經标記過，沒必要再标記。
例如,已知素數7,7*4=28在周遊到4的素因子2時已經将2的14倍，即2*14=28标記過了。
優化的bug:
發現這個bug是因為有道題需要40w以内的素數。n*n不超int時即可，否則需要将for (int k = j*j;k < max;k+=j)的j*j改為j*2等（優化失效），使k的指派不超過int，當然,你可以讓k是其他類型，不過，數大時，埃氏篩法時間複雜度已經不行了。
3.歐拉篩法
時間複雜度：O(n)
歐拉篩法是埃氏篩法的優化，非素數僅被最小素因子标記一次。對于一個非素數，它會被它的素因子标記多次，例如,30=2*15=3*10=5*6，在得到素數2,3,5時均被标記一次，數大時更會标記很多次，做了很多無用功。
/*
素數輸出：輸入一個大于0的整數n，輸出1到n之間（不包括該整數）的所有素數，
空格隔開（最後一個素數後不輸出空格）
Project: 歐拉篩法
Date: 2019/02/28
Author: Frank Yu
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<stack>
#include<iterator>
#include<algorithm>
#include<iostream>
#define F(i,m,n) for(int i=m;i<n;i++)
using namespace std;
int prime[1000001];//存素數
bool vis[1000001];//标記非素數，true表示非素數，即合數
int psize = 0;//已知素數個數
void oula(int n)
{
memset(vis, false, sizeof(vis));//初始化
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= n; i++)
{
if (!vis[i])//是素數
prime[psize++] = i;//儲存素數
for (int j = 0; j<psize && i*prime[j] <= n; j++)
{
vis[i*prime[j]] = true;//找到的素數的倍數不通路
if (i % prime[j] == 0) break;//相對埃氏篩法的優化，保證合數僅被最小質因子标記一次！
}
}
}
int main()
{
int n;
bool output = false;
scanf("%d", &n);
oula(n);
F(i, 0, psize)
{
if (prime[i] < n)
{
if (output)
{
printf(" %d", prime[i]);//輸出空格
}
else
{
printf("%d", prime[i]);
output = true;
}
}
else break;
}
printf("\n");
return 0;
} 關鍵處的解釋（重點）：
i%prime[j]==0時，break跳出循環（i是prime[j]的倍數）。這是為什麼呢？我們假設繼續循環，看看會發生什麼。
假設，當i是prime[j]的k倍時，i = k*prime[j]，此時，如果繼續for循環，j變j+1，接下來的數就會被prime[j+1]标記，
i*prime[j+1] = k*prime[j]*prime[j+1]，prime裡面存的質數，即prime[j]是最小的質因子，prime[j+1]是質因子，某數num=k*prime[j]*prime[j+1]會被prime[j+1]以i倍标記，當i=k*prime[j+1]時，num會再次被prime[j]以k*prime[j+1]倍标記，
違反了歐拉的核心思想，是以才跳出循環。注：num可以分解為多個質因子。
舉個例子 ：i = 4 ，j = 1，prime[j] = 2，此時,4*2=8，即8被最小質因子2用4倍标記了。如果不跳出循環，prime[j+1] = 3，4*3 =6*2 =12，也就是說不跳出循環,12會被質因子3（非最小質因子）用4倍标記，當i為6時,會被最小質因子2以6倍再次标記。
加break時的結果：
加break的結果
不加break的結果