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[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.

Leave a Reply

Your email address will not be published. Required fields are marked *