How to optimize this code further for prime numbers

Reply

Join Date: Sep 2008
Posts: 6
Reputation: cplusplusgeek is an unknown quantity at this point 
Solved Threads: 0
cplusplusgeek cplusplusgeek is offline Offline
Newbie Poster

How to optimize this code further for prime numbers

 
0
  #1
Oct 17th, 2008
Could there be any better ways to determine whether a number is prime or not particularly with respect to code execution.
  1. #include <iostream.h>
  2. #include <conio.h>
  3.  
  4. void PrimeTest(int);
  5.  
  6. main()
  7. {
  8. int num;
  9. cout<<"Enter number: ";
  10. cin>>num;
  11.  
  12. PrimeTest(num);
  13.  
  14. getch();
  15. }
  16.  
  17.  
  18. void PrimeTest(int n)
  19. {
  20. bool isPrime=true;
  21.  
  22. for(short i=2;i<=(n-1);i++)
  23. {
  24. if (n%i==0)
  25. {
  26. isPrime=false;
  27. break;
  28. }
  29. else
  30. {
  31. isPrime=true;
  32. }
  33. }
  34.  
  35. if ((isPrime) || (n<=2))
  36. {
  37. cout<<n<<" is a prime number!";
  38. }
  39. else
  40. {
  41. cout<<n<<" is not a prime number!";
  42. }
  43. }
Reply With Quote Quick reply to this message  
Join Date: Feb 2008
Posts: 114
Reputation: sidatra79 is an unknown quantity at this point 
Solved Threads: 8
sidatra79's Avatar
sidatra79 sidatra79 is offline Offline
Junior Poster

Re: How to optimize this code further for prime numbers

 
0
  #2
Oct 17th, 2008
Hi lets start with code correctness in relationship to standard c++ and improve some parts too

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. bool PrimeTest(int);
  5.  
  6. int main() //prefer int main() instead of void main() or void main(void)
  7. {
  8. int num;
  9. cout<<"Enter number: ";
  10. cin>>num;
  11. if (PrimeTest(num))
  12. cout<<num<<" is a prime number!";
  13. else
  14. cout<<num<<" is not a prime number!";
  15. return 0;
  16. }
  17.  
  18. bool PrimeTest(int n)
  19. {
  20. bool result=true;
  21.  
  22. for(short i=2;i<=(n-1);i++)
  23. {
  24. if (n%i==0)
  25. {
  26. result=false;
  27. break;
  28. }
  29. else
  30. {
  31. result=true;
  32. }
  33. }
  34. return result; //added because must return sth now
  35. }

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:
  1. for (int k=0;k<1000;++k)
  2. {
  3. if (PrimeTest(num))
  4. cout<<num<<" is a prime number!";
  5. else
  6. cout<<num<<" is not a prime number!";
  7. }
with the code i posted and with yours:
  1. for (int k=0;k<1000;++k)
  2. {
  3. PrimeTest(num);
  4. }
and compare
Last edited by sidatra79; Oct 17th, 2008 at 11:22 am. Reason: added some explanation
Reply With Quote Quick reply to this message  
Join Date: Jan 2008
Posts: 119
Reputation: kux is on a distinguished road 
Solved Threads: 10
kux kux is offline Offline
Junior Poster

Re: How to optimize this code further for prime numbers

 
0
  #3
Oct 17th, 2008
Originally Posted by cplusplusgeek View Post
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) .
Reply With Quote Quick reply to this message  
Join Date: Feb 2008
Posts: 114
Reputation: sidatra79 is an unknown quantity at this point 
Solved Threads: 8
sidatra79's Avatar
sidatra79 sidatra79 is offline Offline
Junior Poster

Re: How to optimize this code further for prime numbers

 
0
  #4
Oct 17th, 2008
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.
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:



Other Threads in the C++ Forum
Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC