如何以更有效的方式检查一个数是否为素数？

Question

所以我有以下问题。他们给了我一个包含 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;
}

Answer 1

这里最容易实现的目标是你的停止条件

i <= x/2

可以替换为

i * i <= x

注意确保不会溢出int。这是因为您只需要达到 的平方根x，而不是一半。也许i <= x / i更好，因为这样可以避免溢出；尽管以牺牲部门为代价，这在某些平台上可能相对昂贵。

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