Ad:

C++ Discussion Thread
Unsolved
Views: 834

Oct 17th, 2008

How to optimize this code further for prime numbers

Expand Post »

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

C++ Syntax (Toggle Plain Text)
#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!";  
   }      
}
#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!";  
   }      
}

cplusplusgeek

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since Sep 2008

Permalink

Oct 17th, 2008

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

c++ Syntax (Toggle Plain Text)
#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
}
#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:

c++ Syntax (Toggle Plain Text)
for (int k=0;k<1000;++k)
{
   if (PrimeTest(num))
      cout<<num<<" is a prime number!";
   else
      cout<<num<<" is not a prime number!"; 
}
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:

c++ Syntax (Toggle Plain Text)
for (int k=0;k<1000;++k)
{
   PrimeTest(num);
}
for (int k=0;k<1000;++k)
{
   PrimeTest(num);
}

and compare

Last edited by sidatra79; Oct 17th, 2008 at 11:22 am. Reason: added some explanation

sidatra79

Reputation Points: 46

Solved Threads: 8

Junior Poster

Offline

114 posts
since Feb 2008

Permalink

Oct 17th, 2008

Re: How to optimize this code further for prime numbers

Click to Expand / Collapse Quote originally posted by cplusplusgeek ...

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

kux

Reputation Points: 66

Solved Threads: 11

Junior Poster

Offline

119 posts
since Jan 2008

Permalink

Oct 17th, 2008

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

Last edited by sidatra79; Oct 17th, 2008 at 11:33 am.

sidatra79

Reputation Points: 46

Solved Threads: 8

Junior Poster

Offline

114 posts
since Feb 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: table value

Next Thread in C++ Forum Timeline: Inserting a number to an array

DaniWeb Message

Cancel Changes

User Name
Password