CODEWITHSUNDEEP
c++primes
Andrei Radu
Andrei Radu

Reputation: 109

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

Upvotes: 3

Views: 22053

Answers (9)

K_Bhanu_Prakash
K_Bhanu_Prakash

Reputation: 29

bool isprime(int x)
{
    if(x <= 1) return false;
    if(x == 2 || x == 3) return true;
    if(x % 2 == 0 || x % 3 == 0) return false;
    if((x - 1) % 6 != 0 && (x + 1) % 6 != 0) return false;
    for(int i = 5; i * i <= x; i += 6)
    {
        if(x % i == 0 || x % (i + 2) == 0) return false;
    }
    return true;
}

If prime numbers need to be printed for a particular range or to determine whether a number is prime or not, the sieve of the eratosthenes algorithm is probably preferable as it is very efficient in terms of time complexity O( n * log2( log2(n) ) ), but the space complexity of this algorithm can cause an issue if the numbers are exceeding certain memory limit.

We can optimize this simpler algorithm which has a time complexity of O(n1/2) by introducing few additional checks based on this thoerem as shown in the above isprime code block.

Despite the fact that Sieve of Erathosthenes algorithm is efficient in terms of time complexity under space restrictions, the above provided isprime code block can be utilized, and there are numerous variations of the Sieve of Erathosthenes algorithm that perform considerably better, as explained in this link.

Many more algorithms exist, but in terms of solving coding challenges, this one is simpler and more convenient. You can learn more about them by clicking on the following links:

  1. https://www.quora.com/Whats-the-best-algorithm-to-check-if-a-number-is-prime
  2. https://www.baeldung.com/cs/prime-number-algorithms#:~:text=Most%20algorithms%20for%20finding%20prime,test%20or%20Miller%2DRabin%20method.

Upvotes: 2

Paras Roy
Paras Roy

Reputation: 1

This is a much faster algorithm in my opinion. It works on the Euclidean algorithm to calculate H.C.F. Basically, I check if the HCF of the number AND the consecutively second number is 1; and if the number itself is divisible by either 2 or 3. Don't ask how I mathematically reached the solution, it just struck me :D. The time complexity of this solution is O(log (max(a,b))), which is notably smaller than the time complexity of the program which runs a loop counter 2 to sqrt(n) is O(sqrt(n)).

  #include <iostream>
    using namespace std;
    
    int hcf(int, int);
    
    int hcf(int a, int b)
    {
        if (b == 0)
        {
            return a;
        }
    
        return hcf(b, a % b);
    }
    
    int main()
    {
        int a;
    
        cout << "\nEnter a natural number: ";
        cin >> a;
    
        if(a<=0)
        {
            cout << "\nFor conventional reasons we keep the discussion of primes to natural numbers in this program:) (Read: Ring of Integers / Euclid's Lemma)";
            return 0;
        }
    
        if (a == 1)
        {
            cout << "\nThe number is neither composite nor prime :D";
            return 0;
        }
    
        if (a == 2)
        {
            cout << "\nThe number is the only even Prime :D";
            return 0;
        }
    
        if (hcf(a, a + 2) == 1)
        {
            if (a % 2 != 0 && a % 3 != 0)
            {
                cout << "\nThe number is a Prime :D";
                return 0;
            }
        }
    
        cout << "\nThe number is not a Prime D:";
    
        return 0;
    }

Correct me if I'm wrong. I'm a student.

Upvotes: 0

Bathsheba
Bathsheba

Reputation: 234885

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.

Upvotes: 5

Apurba Roy
Apurba Roy

Reputation: 61

Here is an efficinent way to check prime number.

 bool isPrime(int num) {
        if(num <= 1) return false;
        if (num <= 3)  return true; 
        
        int range = sqrt(num);
        // This is checked so that we can skip 
        // middle five numbers in below loop 
        if (num % 2 == 0 || num % 3 == 0) 
            return false; 
        

        for (int i = 5; i <= range; i += 6) 
            if (num % i == 0 || num % (i + 2) == 0) 
                return false; 
        
        return true;
    }

Upvotes: 3

user13500072
user13500072

Reputation:

A stander way(maybe..?) is just check from i = 0 to the sqrt(number)

bool isPrime(int num){
    if(num == 1) return false;
    for(int i = 2;i<=sqrt(num);i++){
          if(num % i == 0) return false;
    }
    return true;
}

Upvotes: 1

Saurabh Raj
Saurabh Raj

Reputation: 127

Here is one efficient way to check a given number is prime.

 bool isprime(int n) {
    if(n<=1)
        return false;

    if(n<=3)
        return true;

    if(n%2==0||n%3==0)
        return false;

    for(int i=5;i*i<=n;i=i+6) {
        if(n%i==0||n%(i+2)==0)
            return false;
    }

    return true;
}

Upvotes: 0

MSalters
MSalters

Reputation: 180303

Another inefficiency not yet mentioned is existaP(a, li, (li+ls)/2) + existaP(a, (li+ls)/2+1, ls);

In particular, the problem here is the +. If you know existaP(a, li, (li+ls)/2) > 0, then existaP(a, (li+ls)/2+1, ls) no longer matters. In other words, you're currently counting the exact number of unique factors, but as soon as you know a number has at least two factors you know it's not prime.

Upvotes: 0

Alexandru Ica
Alexandru Ica

Reputation: 139

If the numbers are not too big you could also try to solve this using the sieve of Eratosthenes:

#include <iostream>
#include <array>

using namespace std;
constexpr int LIMIT = 100001;
// not_prime because global variables are initialized with 0
bool not_prime[LIMIT];

void sieve() {
    int i, j;
    not_prime[2] = false;

    for(int i = 2; i < LIMIT; ++i) 
        if(!not_prime[i])
            for(int j = i + i; j < LIMIT; j += i) 
                not_prime[j] = true;
}

int existaP(int a[], int li, int ls){
    if(li==ls)
       if(!not_prime[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];

   sieve();

   if(existaP(a,1,n) >= 1) cout << "Y";
   else cout << "N";
   return 0;
}

Basically when you encounter a prime all the numbers that are a multiple of it won't be primes.

P.S.: Acum am vazut ca esti roman :) Poti sa te uiti aici pentru a optimiza si mai mult algoritmul: https://infoarena.ro/ciurul-lui-eratostene

Upvotes: 0

Arnab Sinha
Arnab Sinha

Reputation: 341

Your code will give a wrong answer if n is 1.

Your time complexity can be decreased to sqrt(n) , where n is the number.

Here is the code

bool isPrime(long int n)
{
  if (n == 1)
  {
    return false;
  }
  int i = 2;
  while (i*i <= n)
  {
      if (n % i == 0)
      {
          return false;
      }
      i += 1;
  }
  return true;
}

The "long int" will help to avoid overflow.

Hope this helps. :-)

Upvotes: 0

Related Questions