# 暴力篩選
這種方法我就不多說了，一個數是質數則其只能被 1 和它本身整除，抓住這個特性，從 2 開始遍歷到這個數減 1，如果該數能整除其中任意一個數，則其都不是質數，
如果想篩選某個範圍內的，則遍歷這個區間，從左端點遍歷到右端點，該數是質數則將其標記為 0，遍歷完以後，數組中是 0 的就是合數，非 0 是質數，時間複雜度 O (n2)
- 判斷一個數 n 是否為質數:
for(int i=2;i<n;i++){ | |
if(n%i==0){ | |
break; | |
} | |
} |
- 篩選一個區間的質數
memset(arr,1,sizeof arr); | |
for(int j=x;j<=y;j++){ | |
for(int i=2;i<n;i++){ | |
if(n%i==0){ | |
arr[j]=0; | |
break; | |
} | |
} | |
} |
arr[i]=1 代表質數，否則就是合數。
# 稍加優化
對於一個數其因數一定是成對出現的，例如: 8 的一對因數，就是 2 和 4。
因此如果這個數能被 2 整除則不用判斷能否被 4 整除了，
對於一個合數來說這個性質沒什麼用，因為判斷到能整除 2 就直接 break 了，但若該數是一個質數呢？
那就會把該數從頭到尾都遍歷一遍，假若數據很大時，這是非常消耗時間的，
我們就可以利用因數成對的性質，遍歷到根號 n，為什麼是根號 n，舉個例子，25，一對因數對是 5 * 5，
5 相當於一個分界線，其他的因子一定一個大一個小，這樣就優化了這個算法，時間複雜度是 O (n3/2)。
for(int i=2;i*i<=n;i++){ // 注意這邊是 <= | |
if(n%i==0){ | |
break; | |
} | |
} |
# 質數篩
質數篩，就是從 1 開始的建表
# 埃式篩
學習質數篩之前我們要知道一個任意一個合數都可以轉換成為一個質數和某個數的乘積，
例如: 25 可以轉換成 5*5，偶數可以轉換成 2a，這樣我們其實可以利用這個性質
將一個區間內的所有質數的倍數都標記一下，被標記的數就是合數，剩下的就是質數。
int p[1000]; //p 陣列儲存質數 | |
void prime() | |
{ | |
vis[1]=1; //1 不是質數 | |
for(int i=2;i<=n;i++){ //n 是篩選範圍 | |
if(!vis[i]){ | |
p[++cnt]=i; // 紀錄質數 | |
for(int j=2*i;j<=n;j+=i){ // 這裡有一個優化，j=2*i | |
vis[j]=1; // 標記為質數的倍數 | |
} | |
} | |
} | |
} |
# 歐拉篩
上面講的埃式篩有一個非常大的缺陷，就是會重複標記，例如 12，我們首先用 2 的 6 倍標記了它，之後又用了 3 的 4 倍再次標記，這樣就造成了時間的浪費，
而質數篩本身就是因為時間上的優化才出現的，因此這點必須優化，因此出現了歐拉篩，歐拉篩就是為了解決重複標記的問題。
int vis[maxn],p[maxn/10]; // 質數密度其實不大，可以 / 10 節省空間 | |
int cnt=0; | |
void prime() | |
{ | |
vis[1]=1; | |
for(int i=2;i<=maxn;i++){ | |
if(!vis[i]) p[++cnt]=i; | |
for(int j=1;j<=cnt&&i<=maxn/p[j];j++){ | |
vis[i*p[j]]=1; | |
if(i%p[j]==0) break; // 核心程式碼，如果 i 能整除這個質數就跳出迴圈 | |
} | |
} | |
} |
對於
vis [i*p [j]] = 1的解釋： 這裡不是用i的倍數來消去合數，而是把p裡面紀錄的質數，升序來當做要消去合數的最小質因數。對於
i%p[j] == 0就break的解釋：當i是p[j]的倍數時，i = kp[j]，如果繼續運算j+1，i * p[j+1] = p[ j] * kp[j+1]，這裡p[j]是最小的質因數，當i = k * p[j+1]時會重複，所以才跳出循環。
舉個例子：i = 8，j = 1，p[j] = 2，如果不跳出循環，p[j+1] = 3，8 * 3 = 2 * 4 * 3 = 2 * 12，在i = 12時會計算。
因為歐拉篩法的原理便是通過最小質因數來消除。
