Prime Number Program in C++ with Code

Along the way, we’ll share a few C++ programs that will help you check if a number is prime, print all prime numbers within a certain range, and utilize efficient algorithms to minimize time complexity. This article is tailored for both beginners and those with some experience.

If you’re eager to master C++ programming from the ground up with real-world examples and hands-on projects, consider signing up for the C++ Programming Course in Noida, offered by Uncodemy.

What is a Prime Number?

A prime number is a natural number greater than 1 that can only be divided evenly by 1 and itself. In simpler terms, if a number is only divisible by 1 and itself, it qualifies as a prime number.

Examples of Prime Numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29…

Important Notes:

-        1 is not considered a prime number.

-        2 is the smallest and the only even prime number.

-        Prime numbers are crucial in areas like cryptography, hashing algorithms, and computer security.

How to Check if a Number is Prime in C++?

-        To determine if a number is prime in C++, you should:

-        Take a number as input.

-        Check for divisibility from 2 up to √n.

-        If it’s divisible by any number in that range, it’s not prime.

-        Otherwise, it is a prime number.

Prime Number Program in C++ (Basic Approach)

Let’s kick things off with a straightforward program that checks if a given number is prime.

Program 1: Check Whether a Number is Prime

#include <iostream>

using namespace std;

int main() {

int num, i, flag = 0;

cout << "Enter a positive integer: ";

cin >> num;

if (num <= 1) {

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

     return 0;

}

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

     if (num % i == 0) {

         flag = 1;

            break;

     }

}

if (flag == 0)

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

else

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

return 0;

}

Output:

Enter a positive integer: 13

13 is a prime number.

Optimized Prime Number Program in C++

While the current method works well, it’s not the best choice for larger numbers. We can enhance it by minimizing the number of iterations through square root optimization.

Program 2: Optimized Prime Number Check Using sqrt()

#include <iostream>

#include <cmath>

using namespace std;

bool isPrime(int num) {

if (num <= 1) return false;

if (num == 2) return true;

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

     if (num % i == 0)

            return false;

}

return true;

}

int main() {

int number;

cout << "Enter a number: ";

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: 29

29 is a prime number.

Program to Print Prime Numbers in a Given Range

At times, we need to list all the prime numbers between two specified numbers. Let’s put that into action.

Program 3: Prime Numbers in a Range

#include <iostream>

#include <cmath>

using namespace std;

bool isPrime(int num) {

if (num <= 1)

     return false;

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

     if (num % i == 0)

            return false;

}

return true;

}

int main() {

int lower, upper;

cout << "Enter lower and upper bounds: ";

cin >> lower >> upper;

cout << "Prime numbers between " << lower << " and " << upper << " are: ";

for (int i = lower; i <= upper; i++) {

     if (isPrime(i))

         cout << i << " ";

}

return 0;

}

Output:

Enter lower and upper bounds: 10 50

Prime numbers between 10 and 50 are: 11 13 17 19 23 29 31 37 41 43 47

Why Are Prime Numbers So Important in Programming?

Prime numbers aren't just a topic for math enthusiasts; they play a crucial role in various real-world applications, including:

1. Cryptography

Modern encryption methods, like RSA, depend on large prime numbers to create secure keys.

2. Hashing Algorithms

A lot of hashing techniques and pseudo-random number generators utilize prime numbers to ensure keys are distributed evenly.

3. Competitive Programming

You’ll often encounter prime number logic in coding competitions, especially when faced with challenges that require optimized solutions.

4. Mathematical Computations

Many problems in number theory, such as factorization, GCD, and LCM, rely on prime numbers.

Tips for Optimizing Prime Number Code

-        Instead of looping through n, use sqrt(n) to cut down on iterations.

-        Skip even numbers greater than 2 in your loop.

-        For generating a large number of primes efficiently, consider using the Sieve of Eratosthenes.

Advanced: Sieve of Eratosthenes (Generate All Primes up to N)

This method is one of the quickest ways to find all prime numbers up to a specified limit.

Program 4: Sieve of Eratosthenes in C++

#include <iostream>

#include <vector>

using namespace std;

void sieve(int n) {

    vector<bool> isPrime(n + 1, true);

isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i <= n; i++) {

     if (isPrime[i]) {

         for (int j = i * i; j <= n; j += i)

                isPrime[j] = false;

     }

}

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

     if (isPrime[i])

         cout << i << " ";

}

}

int main() {

int limit;

cout << "Enter the limit: ";

cin >> limit;

cout << "Prime numbers up to " << limit << " are: ";

    sieve(limit);

return 0;

}

Output:

Enter the limit: 100

Prime numbers up to 100 are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Best Practices for Writing Prime Number Code in C++

Learning how to implement prime number programs is essential, but sticking to best practices will help you create code that’s clean, efficient, and ready for any interview.

1. Use Functions to Modularize Your Code

Instead of cramming all your logic into main(), break it up into separate functions like isPrime(). This approach makes your code more reusable and easier to read.

bool isPrime(int n) {

// logic

}

2. Avoid Redundant Checks

For numbers greater than 2, you can skip checking even numbers altogether, which will save you time during iterations.

for (int i = 3; i <= sqrt(n); i += 2)

3. Choose the Right Data Types

When dealing with very large numbers (like up to 10^9 or more), opt for long long instead of int to prevent overflow issues.

long long num;

4. Optimize for Range Queries

If your program needs to check multiple numbers in a range (like from 1 to 10^6), using the Sieve of Eratosthenes is a much faster option than checking each number one by one.

5. Comment Your Code

Adding proper comments helps clarify the flow of your code, especially for beginners or when you come back to it later.

6. Test Edge Cases

Make sure to test your prime number functions against edge cases such as:

-        Negative numbers

-        0 and 1

-        Very large numbers (like 10^9)

-        Special inputs like 2 (the only even prime)

Example:

cout << isPrime(1);   // Not prime

cout << isPrime(2);   // Prime

cout << isPrime(-5);  // Not prime

Conclusion

Grasping and applying prime number programs in C++ is a crucial skill that every budding programmer should aim to master. We’ve explored various methods to determine prime numbers, print number ranges, and implement optimization techniques like the Sieve of Eratosthenes.

Whether you’re gearing up for technical interviews or looking to sharpen your coding skills, practicing prime number logic will definitely boost your problem-solving abilities.

Eager to lay a solid foundation in C++ through hands-on projects and expert guidance? Sign up for the C++ Programming Course in Noida by Uncodemy and kickstart your programming adventure today!

Frequently Asked Questions (FAQs)

Q1. What’s the easiest way to check if a number is prime in C++?

The easiest method is to loop from 2 to n/2 and see if any number divides n. If it does, then it’s not a prime.

Q2. What makes the Sieve of Eratosthenes more efficient?

The Sieve of Eratosthenes improves efficiency by eliminating all multiples of a number in one go, which enhances performance for larger ranges.

Q3. Can the number 1 be considered a prime number?

No, it can’t. By definition, prime numbers must have exactly two distinct divisors, and 1 only has one (itself).

Q4. Why is 2 classified as a prime number?

2 is only divisible by 1 and itself (2), which meets the criteria for a prime number. Plus, it’s the only even prime.

Q5. What’s the time complexity for checking primes using sqrt(n)?

The time complexity is O(√n), which is significantly better than O(n) for larger values.

Q6. Are prime numbers utilized in real-world applications?

Absolutely! They play a vital role in cryptography, hashing, data structures, and even blockchain technology.