所以我有以下问题。他们给了我一个带n个数字的数组,如果使用“ Divide et Impera”包含任何质数,我必须打印。我解决了这个问题,但由于效率不高(他们说),它只能得到70/100。
#include <iostream>
using namespace std;
bool isPrime(int x){
if(x == 2) return false;
for(int i = 2; i <= x/2; ++i)
if(x%i==0) return false;
return true;
}
int existaP(int a[], int li, int ls){
if(li==ls)
if(isPrime(a[li]) == true) return 1;
else return 0;
else return existaP(a, li, (li+ls)/2)+existaP(a, (li+ls)/2+1, ls);
}
int main(){
int n, a[10001];
cin >> n;
for(int i = 1; i<=n; ++i) cin >> a[i];
if(existaP(a,1,n) >= 1) cout << "Y";
else cout << "N";
return 0;
}
最佳答案
最低的挂果是您的有条件停止
i <= x/2
可以替换为
i * i <= x
注意确保您不会溢出
int
。这是因为您只需要上至x
的平方根,而不是一半。您的
x == 2
算法也有问题,因为返回值不正确。如果您放弃了该额外测试,那就更好了,因为随后的循环涵盖了它。关于c++ - 如何更有效地检查数字是否为质数?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/50930926/