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

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.