How to optimize this code further for prime numbers
 

Could there be any better ways to determine whether a number is prime or not particularly with respect to code execution.

#include <iostream.h>

#include <conio.h>



void PrimeTest(int);



main()

{

      int num;

      cout<<"Enter number: ";   

      cin>>num;

      

      PrimeTest(num);

      

getch();

}





void PrimeTest(int n)

{

   bool isPrime=true;

     

     for(short i=2;i<=(n-1);i++)

     {

       if (n%i==0)

       {

          isPrime=false;

          break;           

       }

       else

       {

         isPrime=true;    

       }

     }

     

   if ((isPrime) || (n<=2))

   {

      cout<<n<<" is a prime number!";            

   }

   else

   {

      cout<<n<<" is not a prime number!";  

   }      

}

Re: How to optimize this code further for prime numbers
 

Hi lets start with code correctness in relationship to standard c++ and improve some parts too :D

#include <iostream>

using namespace std;



bool PrimeTest(int);



int main()  //prefer int main() instead of void main() or void main(void)

{

        int num;

        cout<<"Enter number: ";   

        cin>>num;

        if (PrimeTest(num))

                cout<<num<<" is a prime number!"; 

        else

                cout<<num<<" is not a prime number!"; 

        return 0;

}



bool PrimeTest(int n)

{

        bool result=true;



        for(short i=2;i<=(n-1);i++)

        {

                if (n%i==0)

                {

                        result=false;

                        break;           

                }

                else

                {

                        result=true;    

                }

        }

        return result;    //added because must return sth now

}

Keep in mind that important for u is to decrease the execution time of the PrimeTest function. When u included there the cout statements, u added extra overhead of msecs through these into the function. So if u place the call to your PrimeTest within a for loop and repeat the call for 1000 times u will notice a relatively big difference (if u r concerned for msecs time) when including those cout statements within the function. for example try:

for (int k=0;k<1000;++k)

{

   if (PrimeTest(num))

      cout<<num<<" is a prime number!";

   else

      cout<<num<<" is not a prime number!"; 

}

with the code i posted and with yours:

for (int k=0;k<1000;++k)

{

   PrimeTest(num);

}

and compare

Re: How to optimize this code further for prime numbers
 

well, you will defenetly won't find any divisors greater then n/2 !! so, instead of iterating to n-1 you could just iterate to n/2. Another thing would be that if a number doesn't have any divizors from 2 to sqrt(n) than it will not have any above it as well, so you could just iterate from 2 to sqrt(n) .

Re: How to optimize this code further for prime numbers
 

One more think u can do is to apply Wheel factorization based on the Sieve of Eratosthenes.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Here an implementation for sbdy:

an Implemenattion

or use the Sieve of Atkin depending on the total amount of prime numbers that u want to calculate:

http://en.wikipedia.org/wiki/Sieve_of_Atkin