測驗標準
這里使用兩類、五種常用質數判斷演算法進行測驗：列舉因子法（暴力、開方優化、6n再優化）、質數篩（埃氏篩法、歐拉篩法），（Miller-Rabin呢？不會，沒搞懂）
同時，使用兩類情況進行測驗：
- 尋找 2-100,000 內的質數個數
- 尋找 10,000,001-10,009,999 內的質數個數
質數判斷演算法
列舉因子法
1. 暴力遍歷
很顯然，判斷n是不是質數，最簡單的只要暴力從2到n過一遍就可以了
template <class IntT> bool isPrime(IntT n) {
if (n <= 1)
return false;
for (IntT i=2; i<n; i++) {
if (n % i == 0)
return false;
}
return true;
}
分析：最壞情況（是質數）每個都遍歷一遍，時間復雜度\(O(n)\)，平均情況由于質數分布也是\(O(n)\)
2. 開方優化
容易推出，若一個數n不是質數，則它必然有一個因數\(F\le\sqrt{n}\)，因此，只需要判斷 [2-\(\sqrt n\)]之間的數即可，
template <class IntT> bool isPrime(IntT n) {
if (n <= 1)
return false;
for (IntT i=2; i*i<=n; i++) {
if (n % i == 0)
return false;
}
return true;
}
分析：時間復雜度降為\(O(\sqrt n)\)
3. 6n優化
再想一想就會發現，我們對于2、3的倍數做了太多次重復運算：一個數模2不等于0，那么它模4、6、8也都不會等于0；3也一樣，這些重復在6次的周期內會重復4次，因此，我們可以考慮優化它們，即：
除特殊情況外，只需考慮因數為\(6n-1\)和\(6n+1\)的情況（n為正整數）
template<class IntT> bool isPrime(IntT n) {
if (n <= 1)
return false;
if (n <= 5 && n != 4)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (IntT i=5; i*i<=n; i+=6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
分析：雖然時間復雜度沒降，但速度顯著提升了
篩法
這里就不詳細講解了，主要是運用已知的質數遍歷，減少求范圍內質數時重復的遍歷次數（篩法都會更耗空間），
1. 埃氏篩法
（注：這里加了個小小的優化，在第二層回圈里，j初始化為i*i）
template<class IntT> IntT get_primes_num(IntT n) {
if (n <= 1)
return 0;
bool *isPrimes = new bool[n + 1];
IntT *primes = new IntT[n - 1],
pn = 0;
memset(isPrimes, 1, n - 1);
for (IntT i=2; i<=n; i++) {
if (isPrimes[i]) {
primes[pn++] = i;
for (IntT j=i*i; j<=n; j+=i)
isPrimes[j] = false;
}
}
delete isPrimes;
delete primes;
return pn;
}
時間復雜度為\(O(n\ln\ln n)\)（這一堆原理自己搜去，我自己也講不清楚）
2. 歐拉篩法
對于埃氏篩法的進一步優化
template<class IntT> IntT get_primes_num(IntT n) {
if (n <= 1)
return 0;
bool *isPrimes = new bool[n + 1];
IntT *primes = new IntT[n - 1],
pn = 0;
memset(isPrimes, 1, n - 1);
for (IntT i=2; i<=n; i++) {
if (isPrimes[i])
primes[pn++] = i;
for (IntT j=0; i*primes[j]<=n; j++) {
isPrimes[i * primes[j]] = false;
if (i % primes[j] == 0)
break;
}
}
delete isPrimes;
delete primes;
return pn;
}
時間復雜度為\(O(n)\)，注意：在n不大的時候，歐拉篩法與埃氏篩法比并不具有絕對優勢，還有可能被反超（畢竟只是優化了個\(\ln\ln n\)），幾乎相當于拼常數
測驗
好了，接下來就是我們的核心——測驗環節了，我這里在本機使用了一個基于std::chrono的封裝計時庫（程式主體部分運行至少6s），記錄以微秒（μs，百萬分之一秒）為單位，
（windows x64 AMDRyzen5-5600H）
回顧一下兩種情況：
- 尋找 2-100,000 內的質數個數
- 尋找 10,000,001-10,009,999 內的質數個數
（篩法：你故意找茬是吧）
| 平均用時(μs) | 情況1 | 情況2 |
|---|---|---|
| 暴力遍歷 | 647,400 | 8,800,000 |
| 平方優化 | 3,985 | 3,496 |
| 6n優化 | 1,363 | 1,163 |
| 埃氏篩 | 154.5 | 35,000 |
| 歐拉篩 | 265.5 | 50,000 |
總結
平時做演算法題的時候，如果說是從1或者一個較小的數開始計數的，那么建議使用埃氏篩（歐拉篩實作起來更煩，還不一定拼得過加了優化的埃式篩法（ps：優化加了容易資料容易溢位，建議用unsigned long long），要么去掉優化老老實實用j=2i）；
反之，如果是都在一個較高位的，那么建議使用6n優化，容易寫，比平方優化效率也高很多，這時候再使用兩次篩法的差值，時間就容易爆掉（就算一次也容易爆時間），
好了，以上就是本人對C++質數判斷演算法的時間測驗的所有內容了，初次創作，如有錯誤歡迎指出ヾ(^▽^*)))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/498405.html
標籤：C++