演算法競賽入門 — 素數篩
α. 何謂素數？
素數，也就是我們常說的質數，官方解釋為在大于1的自然數中，除了1和它本身以外不再有其他因數的自然數.
β. 如何判斷其是否為素數？
β1. 初始版本
由定義知，對于一個自然數n, 如果從 2 - n -1之間的任意數 i，n均不能被 i 整除,則 n 為素數. 于是通過一個很簡單的for回圈，我們便很容易的寫出來最簡單的素數判斷函式！
bool isPrime(int num){
for(int i = 2;i < num;i++){
if(num % i == 0)
return false;
}
return true;
}
β2. 加強版
我們來接著想一下，如果我們對一個數進行判斷，最好情況下是被 2 整除后直接被判斷為非素數，最壞情況下為遍歷一遍判斷為素數，所以在不考慮素數與非素數的個數占比的差異的情況下，我們可以大致認為平均下來時間復雜度為O(n/2).
對于一個自然數 n, 如果存在 a * b == n （a <= b）,那么必定
存在以下結論：
b >= sqrt(n)
同時， 對于一個合數，例如 :
在利用 for 回圈進行遍歷的時候，如果 3 可以將 12 整除 .那么，就可以認定 12 為 合數. 換一種思想，對于一個素數來講，如果在(int)sqrt(n)+1 之前都沒有 i 將其整除，那么之后的 i 也就不會有資料會將其整除，因為 如果 6 可以 將 12 整除， 那么 2 肯定也是可以的. 所以，對于 for 回圈的迭代次數我們可以有理論依據的將其減少,得到以下的更高效率的代碼
bool isPrime(int num){
for(int i = 2;i * i < num;i++){ // i <= (int)sqrt(num) + 1 也可
if(num % i == 0)
return false;
}
return true;
}
γ. 素數篩
γ1. 打表
這個名詞對于參加過一些程式設計比賽的同學應該不會陌生，所謂打表就是講一些資料預先存起來，在程式運行的時候直接訪問，得到一個O(1)的可觀時間.
就拿我們這個判斷素數來說吧，對于一個程式程式設計比賽來說，資料量是比較大的，如果我們在素數問題上一次又一次的判斷，那么一般都會TLE的，因此我們引入了這樣一個思想——>空間換時間，即使用一個陣列來存盤每個數的狀態（是否為素數），這樣就可以實作 O(1) 的時間復雜度了.
int isPrime[10] = {0,1,1,1,0,1,0,1,0,1}; //此處列出了0-9 十個數的素數狀態
γ2. 埃氏篩
然而還有一個問題沒有解決,對于幾十幾百的數，我們還是有那么一點點的精力來預先存盤每個數的狀態的，但對于很大的資料來說，我們還是束手無策的，因此，素數篩就排派上了很大的用場.素數篩有很多種，這里只給大家講一種最基本的埃氏篩
思路參考了下面這篇博客,以下為核心思想：
想更深層了解 請戳這篇博客
從2開始 2是素數 那么4不是 6不是 8也不是 10、12、14、16、18、20 都不是 這是9次操作
然后 3 開始 6 9 12 15 18 都不是素數 這是5次操作
然后4 跳過 5 跳過 6 跳過
從7開始 14 不是素數 這是1次操作
后邊的 8 9 10 11 12 14 15 16 18 20 都會跳過
而11 13 17 19 都不會操作 因為他們的倍數 大于20了
其中核心思想是如果一個數確定為素數，那么其倍數（2，3，4，…）都不會為素數！
廢話不多說了，還是上代碼吧~
//
// Created by 29273 on 2020-07-26.
//
#include <iostream>
#include <set>
#include <unordered_map>
#include <map>
#include <cctype>
#include <algorithm>m
#include <string.h>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;
#define maxNum 10000
int prime[maxNum]; // 將素數從小到大存盤起來
bool isPrime[maxNum]; // 存盤每一個數
int countN;
void Prime(int n){ //埃氏篩
countN = 0;
for(int i = 2;i <= n;i++){
if(!isPrime[i]){
prime[countN++] = i;
}
for(int j = 2; j * i <= n;j++){
isPrime[j*i] = true;
}
}
}
int main(){
Prime(1000);
for(int i = 0;i <= countN;i++){
printf("%d ",prime[i]);
}
return 0;
}
相較于我們對每一個數通過函式進行判斷然后存盤狀態的方法，在之前那篇博客中實驗證明過，埃氏篩確實節省了很多的時間.
溫馨提示：使用素數篩還是需要要看情況的，比如題目資料最大為1e6 ，那么我們的引數 maxNum 肯定是需要調整的，如果為 maxNum == 1e7 會造成不必要的時間浪費.
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/121590.html
標籤：其他
上一篇：深度學習入門（上）