给定 n 个数,要求判断这n个数是否为质数,若是,则输出Yes, 若不是,则输出No
时间: 2023-05-11 09:04:04 浏览: 55
C++如何判断一个数字是否为质数
5星 · 资源好评率100%
可以使用质数判断的常见算法,例如试除法或者埃氏筛法。以下是一个使用试除法的示例代码:
#include <iostream>
using namespace std;
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;
}
int main() {
int n;
cin >> n;
bool allPrime = true;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (!isPrime(x)) allPrime = false;
}
if (allPrime) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
注意,这个算法的时间复杂度是 O(n * sqrt(n)),如果 n 很大,可能会超时。可以使用更高效的算法,例如 Miller-Rabin 算法,但是实现起来比较复杂。
阅读全文