| | |
How to optimize this code further for prime numbers
Please support our C++ advertiser: Intel Parallel Studio Home
![]() |
•
•
Join Date: Sep 2008
Posts: 6
Reputation:
Solved Threads: 0
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!"; } }
Hi lets start with code correctness in relationship to standard c++ and improve some parts too 
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:
with the code i posted and with yours:
and compare

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 }
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!"; }
c++ Syntax (Toggle Plain Text)
for (int k=0;k<1000;++k) { PrimeTest(num); }
Last edited by sidatra79; Oct 17th, 2008 at 11:22 am. Reason: added some explanation
•
•
Join Date: Jan 2008
Posts: 119
Reputation:
Solved Threads: 10
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) .
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
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.
![]() |
Other Threads in the C++ Forum
- Previous Thread: table value
- Next Thread: Inserting a number to an array
| Thread Tools | Search this Thread |
Tag cloud for C++
6 add api array arrays assignment beginner binary bitmap c++ c/c++ calculator char class classes code compile compiler console conversion convert count data database delete desktop developer directshow dll encryption error file forms fstream function functions game generator getline givemetehcodez graph homeworkhelper iamthwee ifstream input int integer java lazy lib linux loop looping loops map math matrix memory multidimensional newbie news node number output parameter pointer problem program programming project proxy python random read recursion recursive reference return sort string strings struct studio system template templates text tree url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets





