所以我有以下问题。他们给了我一个带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/

10-11 22:45
查看更多