在C++中,有多種方法可以用來測試一個數是否為素數。以下是一些常見的方法的比較:
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
bool isPrime(int n) {
if (n <= 1) return false;
vector<bool> isPrime(n+1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i*i <= n; i++) {
if (isPrime[i]) {
for (int j = i*i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
return isPrime[n];
}
根據以上的比較,可以看出厄拉托斯特尼篩法是最有效的方法,適用于篩選一定范圍內的所有素數,而在單個數的素數測試中,優化的窮舉法可能是更好的選擇。