How to check if a number is prime in a more efficient manner?

Question

So I have the following problem. They give me an array w/ n numbers and I have to print if it contains any prime numbers using "Divide et Impera". I solved the problem but it gets only 70/100 because it isn't efficient(they say).

#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

The lowest hanging fruit here is your stopping conditional

i <= x/2

which can be replaced with

i * i <= x

having taken care to ensure you don't overflow an int.This is because you only need to go up to the square root of x, rather than half way. Perhaps i <= x / i is better still as that avoids the overflow; albeit at the expense of a division which can be relatively costly on some platforms.

Your algorithm is also defective for x == 2 as you have the incorrect return value. It would be better if you dropped that extra test, as the ensuing loop covers it.