素數的判定
試除法
（1）普通
復雜度：$O(n)$
bool prime(int x){//判斷x是不是質數，是回傳true，不是回傳false if(x <= 1) return false; for(int i = 2; i < x; i ++){ if(x % i == 0) return false; } return true; }
（2）改進
復雜度：$O(\sqrt{n})$
bool prime(int x){ if(x <= 1) return false; for(int i = 2; i <= sqrt(x); i ++){ if(x % i == 0) return false; } return true; } //用乘法可以避免根號的誤差 bool prime(int x){ if(x <= 1) return false; for(int i = 2; i * i <= x; i ++){ if(x % i == 0) return false; } return true; }
根據題目不同，有可能你需要先預處理出 $1\sim N$這$N$個數是否是素數，就是俗稱的打表，再用上面的這些方法，復雜度就是$O(\sqrt{n})$，如果$N$特別大，就比較慢了，
埃式篩
原理：質數的倍數都不是質數
比如$2$是質數，那么$4,6,8,10,12...$都不是質數
然后看$3$是質數，那么$6,9,12,15,18,21...$都不是質數
然后看$4$，$4$已經被$2$標記為合數了，所以跳過
然后看$5$這樣一直回圈下去，
時間復雜度：$O(nloglogn)$
const int N = 100000 + 5; bool P[N]; int total,prime[N];//就往大了開，反正不用的不算記憶體 void AiSieve() { for (int i = 2; i < N; i++) { if (!P[i]) { prime[total++] = i; for (int j = i * 2; j < N; j += i) { P[j] = true; } } } }
線性素數篩選（歐拉篩）
在埃氏篩法的思想上，這個方法可以保證每個合數都被它最小的質因數篩去，所以一個數只會經過一次，
比如$12$，既是$2$的倍數，也是$3$的倍數，在埃氏篩中，會被$2$和$3$篩選兩次，而在歐拉篩中$12$只會被$6*2$篩選，而不會被$4*3$篩選，
時間復雜度為$O(n)$，其實對于埃氏篩，$loglogn$非常小，我們能碰到的問題級別，區別其實不太大（loglog(10^10) ≈ 5.2），把埃篩看成線性也無妨，畢竟好寫，很大，差了好幾倍，
核心思想：
紅色標注的地方是整個演算法的靈魂，保證每個合數被它最小的質因數篩去，
$i\ \%\ prime[j]==0$，就是如果出現 $prime[j]\ |\ i$，
那么一定有
$prime[j]\ |\ i*prime[j+1]，prime[j]\ |\ i*prime[j+2]\ ...\ prime[j]\ |\ i*prime[tot-1]$
舉個例子，對著上面的來，i = 6時，（此時小于$6$的質數都被裝進prime里）
$6\ \%\ 2==0$，說明$2\ |\ 6$
那么一定有
$2\ |\ 6*3$，$2\ |\ 6*5$
也就是說$18$和$30$都有最小質因數$2$，$18=9*2,\ 30=15*2$，所以跳出回圈，保證每個合數被它最小的質因數篩去，
const int N = 100000 + 5; bool M[N];//prime[i]表示i是不是質數 int prime[N], tot;//p[N]用來存質數 void EulerSieve() { for (int i = 2; i < N; i++) { M[i] = true; } for (int i = 2; i < N; i++) { if (M[i]) prime[tot++] = i;//把質數存起來 for (int j = 0; j < tot && i * prime[j] < N; j++) { M[i * prime[j]] = false; if (i % prime[j] == 0) break; } } }
拓展應用
上述演算法的除去打素數表，我們可以根據演算法的思想做一些別的事情，
（1）埃氏篩，獲取$1\sim N$數的所有素因子
const int N = 100000 + 5; vector<int> prime_factor[N]; void get_prime_factor() { for (int i = 2; i < N; i++) { if (prime_factor[i].size() == 0) {//如果i是質數 for (int j = i; j < N; j += i) { prime_factor[j].push_back(i); } } } }
（2）埃氏篩，獲取1~N數的所有素因數分解
const int N = 100000 + 5; vector<int> prime_factor[N]; void factorization() { for (int i = 2; i < N; i++) { if (prime_factor[i].size() == 0) {//如果i是質數 for (int j = i; j < N; j += i) { int temp = j; while (temp >= i) { if (temp % i == 0) { prime_factor[j].push_back(i); temp /= i; } else break; } } } } }
Miller - Rabin素數測驗
本段落參考：http://www.matrix67.com/blog/archives/234
費馬小定理：
若$p$是質數，且$gcd(a,p) = 1$，那么$a^{p-1}mod\ p=1$
根據逆反命題的等價性，不滿足$2^{(n-1)} mod\ n = 1$的$n$一定不是素數；如果滿足的話則多半是素數，那么如果我只計算$2^{(n-1)} mod\ n$的值，那么素性判斷出錯的概率有多少？在前10億個自然數中共有50847534個素數，而滿足$2^{(n-1)} mod\ n = 1$的合數n有5597個，這樣算下來，演算法出錯的可能性約為0.00011，這個概率太高了，我們剛才只考慮了$a=2$的情況，對于式子$a^{(n-1)} mod\ n$，取不同的a可能導致不同的結果，一個合數可能在$a=2$時通過了測驗，但$a=3$時的計算結果卻排除了素數的可能，于是，人們擴展了偽素數的定義，稱滿足$a^{(n-1)} mod\ n = 1$的合數n叫做以a為底的偽素數，前10億個自然數中同時以2和3為底的偽素數只有1272個，這個數目不到剛才的$\frac{1}{4}$，這告訴我們如果同時驗證$a=2$和$a=3$兩種情況，演算法出錯的概率降到了0.000025，容易想到，選擇用來測驗的a越多，演算法越準確，通常我們的做法是，隨機選擇若干個小于待測數的正整數作為底數a進行若干次測驗，只要有一次沒有通過測驗就可以判定不是素數，這就是費馬素性測驗，
但是居然就有這樣的合數，假設為n，它可以通過所有a（小于n，且滿足$(gcd,n)=1$的數）的測驗（這個說法不準確，詳見我在地核樓層的回復），而且第一個這樣極端的偽素數小得驚人，僅僅是一個三位數，561，前10億個自然數中這樣的數有600多個，
Miller和Rabin兩個人的作業讓Fermat素性測驗邁出了革命性的一步，建立了傳說中的Miller-Rabin素性測驗演算法，新的測驗基于下面的定理：
二次探測定理：
若$p$為質數，$x^{2}\equiv 1(mod\ )p$，則有$x\equiv (mod\ p)$或$x\equiv p-1(mod\ p)$
演算法描述：
Miller-Rabin素性測驗同樣是不確定演算法，我們把可以通過以a為底的Miller-Rabin測驗的合數稱作以a為底的強偽素數，第一個以2為底的強偽素數為2047，第一個以2和3為底的強偽素數則大到1 373 653，對于大數的素性判斷，目前Miller-Rabin演算法應用最廣泛，一般底數仍然是隨機選取，但當待測數不太大時，選擇測驗底數就有一些技巧了，比如，如果被測數小于4 759 123 141，那么只需要測驗三個底數2, 7和61就足夠了，當然，你測驗的越多，正確的范圍肯定也越大，如果你每次都用前7個素數(2, 3, 5, 7, 11, 13和17)進行測驗，所有不超過341 550 071 728 320的數都是正確的，如果選用2, 3, 7, 61和24251作為底數，那么$10^16$內唯一的強偽素數為46 856 248 255 981，這樣的一些結論使得Miller-Rabin演算法在OI中非常實用，通常認為，Miller-Rabin素性測驗的正確率可以令人接受，隨機選取k個底數進行測驗演算法的失誤率大概為$4^{-k}$，
完整代碼：
#include <iostream> #include <math.h> #include <time.h> using namespace std; int prime[5] = { 2, 3, 7, 61,24251 }; long long quickPower(long long down, long long e, long long mod) { long long a = down, res = 1; while (e) { if (e & 1) res = ((res % mod) * (a % mod)) % mod; a = ((a % mod) * (a % mod)) % mod; e >>= 1; } return res; } bool MillerRabin(long long p) { if (p == 1 || p == 0)return false; for (int i = 0; i < 5; i++) { if (p == prime[i])return true; if (p % prime[i] == 0 || p < prime[i])return false; int a = i, e = p - 1; if (p % prime[i] == 0 || e & 1)return false; while (!(e & 1)) { int res = quickPower(a, e, p); if (res == 1) e /= 2; else if (res == p - 1) return true; else return false; } } return true; } int main() { long long N; while (cin >> N) { if (MillerRabin(N)) { cout << "Y" << endl; } else cout << "N" << endl; } }
素數的一些神奇性質
（1）所有大于$2$的素數都可以唯一地表示成兩個平方數之差，
證明如下：
（2）麥森數
如果$2^{p}-1$是素數，其中指數$p$一定也是素數，
證明如下：
原命題的逆否命題為：如果$p$不是素數，則$2^{p}-1$不是素數，
如果p不是素數，可以假設 $p=m\cdot n$
$2^p-1=(2^m)^{n}-1=(x-1)(x^{n-1}+x^{n-2}+...+1), x=2^m$
逆否命題成立，原命題成立，
拓展：
求$2^{p}-1$的位數，$2^{p}-1$和$2^{p}$的位數是相同的，因為$2^{p}$最后一個一定不為$0$，可以直接求$2^{p}$的位數，設$k=2^{p}$，根據$10^n$的位數為$n+1$，只要想辦法把$k=2^{p}$中的底數$2$轉換成$10$，指數$+1$就是位數了，根據$10^{log_{10}{2}}=2$，于是$k=(10^{log_{10}{2}})^p$，把$p$乘進去就是$k=10^{p\cdot log_{10}{2}}$，所以位數就是$p\cdot log_{10}{2}+1$（cmath中自帶log10()函式）
（3）當$n$為大于$2$的整數時，$2^{n}+1$和$2^{n}-1$兩個數中，如果其中一個數是素數，那么另一個數一定是合數，
證明如下：
$2^n$一定不能被$3$整除
如果$ (2 ^ {n} \% 3 == 1)$，則一定有：$2 ^{ n} - 1 \% 3 == 0$；
如果 $(2 ^ {n} \% 3 == 2)$，則一定有：$2 ^{ n} + 1 \% 3 == 0$;
也就是說，$2^{n}+1$和$2^{n}-1$中至少有一個是合數，
（4）大于$3$的素數一定是$6$的倍數$ ±1 $
證明如下：
素數$±1$必然是偶數，一定可以被2整除
素數除以$3$，如果余$1$，減$1$后余$0$,；如果余$2$，加$1$后余$0$，即可以素數$±1$后被$3$整除
結合上面兩行，素數$±1$，一定可以被$6$整除
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139443.html
標籤：其他
下一篇：演算法天天練334：字串翻轉