Member Avatar for cplusplusgeek

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
  • 199 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by sidatra79

Dani AI

Generated

Building on 's original question and the useful fixes from and : use a standards-compliant int main(), keep I/O out of the primality routine, and avoid reassigning a flag inside the loop — return as soon as a divisor is found. Also explicitly handle small inputs (n < 2, n == 2, n == 3) before the loop.

A compact, practical improvement is the 6k ± 1 test: after checking 2 and 3, only test potential divisors of the form 6k-1 and 6k+1 up to sqrt(n). Using integer bounds avoids floating-point sqrt and helps prevent overflow.

#include <cstdint>

bool isPrime(uint64_t n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    for (uint64_t i = 5; i <= n / i; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

Practical notes and trade-offs: use uint64_t (or a big-int library for very large values) and prefer i <= n / i over i * i <= n to avoid overflow. For many repeated tests over a range, a sieve (bitset or segmented sieve) will be far faster than calling a per-number test repeatedly. For huge single numbers, use a Miller–Rabin implementation with deterministic witness sets for 32-/64-bit ranges. Compile with optimizations (e.g., -O2/-O3) and profile with std::chrono before chasing micro-optimizations.

Common pitfalls: using short for the divisor (overflow), leaving I/O inside the inner loop, treating 1 or negatives as prime, and relying on sqrt each iteration. Apply the small fixes suggested by and the sqrt-bound idea from , then pick the algorithm (trial division vs. sieve vs. probabilistic test) that matches how many numbers you must check.

Recommended Answers

All 3 Replies

Member Avatar for 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

Member Avatar for kux

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.