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
4
Views
9 Years
Discussion Span
Last Post by 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

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

One more think u can do is to apply Wheel factorization based on the 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:

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.