| | |
How to optimize this code further for prime numbers
![]() |
•
•
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 |
api array based binary bitmap business c++ c/c++ char class classes code coding commentinghelp compile console conversion count decide delete deploy desktop developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez graph guess gui homeworkhelp homeworkhelper iamthwee ifpug ifstream incrementoperators infinite input int integer java lib linkedlist linker loop looping loops map math matrix memory multiple news node number numbertoword output parameter pointer problem proficiency program programming project python random read recursion reference rpg string strings temperature template templates test text text-file tree url variable vector video win32 windows winsock word wordfrequency wxwidgets





