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

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;
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

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.

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