How to optimize this code further for prime numbers

[cplusplusgeek]

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

[sidatra79]

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

[kux]

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

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

[sidatra79]

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