Member Avatar for 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!";  
   }      
}
  • 3 Contributors
  • 3 Replies
  • 180 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by sidatra79
Member Avatar for 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

Member Avatar for 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) .

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.