Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Algorithm to Check Prime Numbers in C++
2.1.
C++
3.
Prime Number Program in C++
3.1.
C++
4.
Complexity Analysis
4.1.
Basic Approach
4.2.
Optimized Approach
5.
Frequently Asked Questions
5.1.
Why do we only check up to the square root of a number to determine if it's prime?
5.2.
Can even numbers be prime?
5.3.
How does optimizing the prime number check improve performance?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Prime Number Program in C++

Author Ravi Khorwal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

When we talk about building blocks in math, prime numbers hold a special place. They are the atoms of mathematics, indivisible & foundational. Prime numbers are those exclusive numbers greater than 1 that are divisible only by 1 & themselves. Why does this matter in programming, especially in C++? It's a gateway to understanding more complex algorithms & cryptographic systems used in real-world applications. 

Prime Number Program in C++

In this article, we'll explore the interesting world of prime numbers in C++. We'll start with the basics, crafting an algorithm to check for prime numbers, then look into writing a prime number program in C++, & finally, analyze the complexity of our solutions. 

Algorithm to Check Prime Numbers in C++

To determine if a number is prime in C++, we start with a straightforward approach. The essence of our strategy is simple: we check if our number can be divided evenly by any other number apart from 1 and itself. If we find such a divisor, the number is not prime. Otherwise, it is a prime number. Let's break down the steps:

  • Start with 2: We begin our check from the number 2, the smallest prime number.
     
  • Divide & Check: We divide our target number by every number starting from 2 up to one less than the target number. For example, if we're checking if 5 is prime, we divide it by 2, 3, and 4.
     
  • Find a Divisor?: If any of these divisions results in a whole number (meaning the remainder is 0), our number isn't prime.
     
  • Complete the Loop: If we go through all potential divisors and find no even division, our number stands as a prime.
     

This approach is straightforward but not the most efficient, especially for large numbers. However, it's a solid starting point for understanding how prime number checks work in programming.

Here's how you might write this algorithm in C++:

  • C++

C++

#include <iostream>

using namespace std;




bool isPrime(int num) {

   if (num <= 1) return false; // Numbers less than or equal to 1 are not prime




   for (int i = 2; i < num; i++) {

       if (num % i == 0) {

           return false; // Found a divisor, not prime

       }

   }

   return true; // No divisors found, it's prime

}




int main() {

   int number;

   cout << "Enter a number to check: ";

   cin >> number;




   if (isPrime(number)) {

       cout << number << " is a prime number.";

   } else {

       cout << number << " is not a prime number.";

   }

   return 0;

}

Output

Enter a number to check: 11
11 is not a prime number


In this example, isPrime is a function that takes an integer num and returns true if num is prime, and false otherwise. The main function asks the user for a number, checks if it's prime, and outputs the result. This code is a basic implementation and works well for small to moderately large numbers.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Prime Number Program in C++

Now that we understand the basic algorithm for checking prime numbers, let's refine our approach for better efficiency. One key improvement is to only check divisors up to the square root of the target number. Why the square root? Because if a number is divisible by another number larger than its square root, the resulting quotient would be less than the square root, meaning we would have already considered it as a divisor. This significantly reduces the number of iterations, especially for large numbers.

Here's how we can implement this optimized approach in a C++ program:

  • C++

C++

#include <iostream>

#include <cmath> // For the sqrt function

using namespace std;




bool isPrimeOptimized(int num) {

   if (num <= 1) return false; // Numbers less than or equal to 1 are not prime

   if (num == 2) return true; // 2 is a prime number

   if (num % 2 == 0) return false; // Exclude even numbers greater than 2




   for (int i = 3; i <= sqrt(num); i += 2) { // Only check odd numbers up to the sqrt of num

       if (num % i == 0) {

           return false; // Found a divisor, not prime

       }

   }

   return true; // No divisors found, it's prime

}




int main() {

   int number;

   cout << "Enter a number to check: ";

   cin >> number;




   if (isPrimeOptimized(number)) {

       cout << number << " is a prime number.";

   } else {

       cout << number << " is not a prime number.";

   }

   return 0;

}

Output

Enter a number to check: 56
56 is not a prime number


In this version, isPrimeOptimized first handles special cases: numbers less than 2, the number 2 itself, and even numbers greater than 2. Then, it iterates from 3 up to the square root of the number, checking only odd divisors. This is because, after excluding 2, no prime number can be even.

This program is more efficient than our first example and can quickly determine if a number is prime, even for larger integers. It's a great example of how a small change in the algorithm can lead to significant improvements in performance.

Complexity Analysis

When we talk about complexity analysis in programming, we're looking at how efficiently a program runs, especially as the size of its input grows. For our prime number checks in C++, this boils down to understanding how many steps our program takes to confirm if a number is prime, depending on the size of that number.

Basic Approach

In our first example, where we checked every number up to n - 1 to see if n is prime, the complexity is straightforward. For each number n, we perform n - 2 checks (since we start at 2 and go up to n - 1). This gives us a time complexity of O(n). In simpler terms, if the number to be checked doubles, the time it takes to check also doubles. This linear relationship is easy to understand but not efficient for large numbers.

Optimized Approach

The second example, where we only check up to the square root of n, significantly reduces the number of steps. Instead of checking n - 2 numbers, we check approximately sqrt(n) numbers. This change brings our complexity down to O(sqrt(n)). In practice, this means that even if the number to check becomes four times larger, the time it takes to check it only doubles. This is a substantial improvement, especially when dealing with very large numbers.

Understanding complexity is crucial because it helps us write programs that run efficiently, even with large inputs. In the context of prime numbers, moving from a basic to an optimized approach can make the difference between a program that runs in a reasonable time and one that takes far too long to be practical.

Frequently Asked Questions

Why do we only check up to the square root of a number to determine if it's prime?

Checking up to the square root simplifies the process because if a number has a factor greater than its square root, the corresponding factor would be less than the square root, and we would have already encountered it.

Can even numbers be prime?

Except for the number 2, which is the only even prime number, no other even numbers can be prime. This is because all even numbers greater than 2 can be divided by 2, which means they have at least one divisor other than 1 and themselves.

How does optimizing the prime number check improve performance?

Optimizing the prime number check, particularly by only considering odd numbers and limiting checks to the square root of the target number, significantly reduces the number of operations required. This makes the program run faster and more efficiently, especially with larger numbers.

Conclusion

In this article, we've taken a thorough look into prime numbers in C++, starting from a basic understanding to developing an efficient program for prime number checks. We began by exploring what prime numbers are and why they're important, followed by a basic algorithm for checking prime numbers. We then enhanced our approach to create an optimized C++ program that efficiently determines if a number is prime by checking divisors only up to the square root and excluding even numbers.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Previous article
sleep() Function in C++
Next article
Endl Mean in C++
Live masterclass