定義
質數是指在大于1的自然數中，除了1和它本身以外不再有其他因數的自然數，
實作
直觀的方法
int isprime(int x) {
if (x < 2) return false; // 小于2的數都不是質數
for (int i = 2; i < x; i++)
if (x % i == 0) return false;
return true;
}
顯然這個演算法的復雜度為\(O(N)\)，
更快的方法
我們知道，一個數如果可以進行因數分解，那么分解時得到的兩個數一定是一個小于等于\(sqrt(n)\)，一個大于等于\(sqrt(n)\)，所以，回圈沒有必要從\(2\)到\(x-1\)，只需要從\(2\)到\(sqrt(n)\)就好了，那么這個演算法的時間復雜度就為\(O\left(sqrt(n)\right)\)，
int isprime(int x) {
if (x < 2) return false; // 小于2的數都不是質數
for (int i = 2; i <= int(sqrt(x)); i++) // 從2到sqrt(x)
if (x % i == 0) return false;
return true;
}
當然，這個演算法還可以繼續優化，我們可以判斷2是不是這個數的約數，然后就可以從\(3\)開始回圈到\(sqrt(n)\)了，每次回圈\(i+2\)，那么這個演算法的復雜度就為\(O(sqrt(n)/2)\)，
int isprime(int x) {
if (x < 2) return false; // 小于2的數都不是質數
if (x != 2 && x % 2 == 0) return false; // 不是2且能被2整除的數都不是質數
for (int i = 3; i <= int(sqrt(x)); i += 2) // 每次回圈加2
if (x % i == 0) return false;
return true;
}
還有更快的嗎？——埃拉托斯特尼篩法
即使是上述的演算法，在遇到很大的數字\((n\ge{100,000,000})\)的時候，還是很慢，
那還有沒有更快的演算法呢？答案是有的，埃拉托斯特尼篩法就是其中之一，
我們可以把從\(2\)到\(maxn\)的數儲存為一張表，例如bool prime[MAXN];，
然后我們遍歷這個陣列，把\(i\)的倍數從陣列中去掉，這樣我們就得到了一張從\(2\)到\(maxn\)的質數的表，
需要判斷一個數是否為質數的時候只需要查詢這張表就可以了，例如if (prime[i]) // 你的操作，
void getPrime(int maxn) {
for (int i = 0; i <= maxn; i++) prime[i] = 1; // 全部定義為質數
prime[0] = prime[1] = 0;
for (int i = 2; i <= maxn; i++) {
if (!prime[i]) continue;
for (int j = i * 2; j <= maxn; j += i) prime[j] = 0; // i的倍數標記為合數
}
}
參考
素數的四種判斷方法、實作及比較：https://blog.csdn.net/zhanshen112/article/details/90574455
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30660.html
標籤：C++
上一篇：P1358 撲克牌