c++ - 如何以更有效的方式检查数字是否为素数？

Question

所以我有以下问题。他们给了我一个有数字的数组，如果它包含任何素数，我必须使用“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;
}

Answer 1

这里最容易挂的果子是你的停止条件

i <= x/2

可以替换为

i * i <= x

注意确保您不会溢出 int .这是因为你只需要去到x的平方根，而不是半途而废。也许i <= x / i更好的是避免溢出；尽管以在某些平台上成本相对较高的部门为代价。

您的算法对于 x == 2 也有缺陷因为你有不正确的返回值。如果你放弃那个额外的测试会更好，因为随后的循环会覆盖它。