C++ Program to Print Prime Numbers in a Range

C++ Program to Print Prime Numbers in a Range

By /

Prime numbers are numbers greater than 1 that have no divisors other than 1 and themselves. They are essential in mathematics, cryptography, and computer algorithms. Printing all prime numbers within a specific range is a common beginner exercise in C++. It helps you understand loops, conditionals, and optimization strategies while practicing fundamental programming skills. In this article, we will explore several methods to print prime numbers in a range, explained in a beginner-friendly manner.

Program 1: Basic Method to Print Prime Numbers

This is the simplest way to print prime numbers in a given range. The program checks every number from the starting point to the endpoint and determines if it is prime using a basic loop.

#include <iostream>

using namespace std;

int main() {

    int start, end;

    cout << "Enter the range (start and end): " << endl;
    cin >> start >> end;

    for(int n = start; n <= end; n++) {

        bool isPrime = true;

        if(n <= 1) isPrime = false;

        else {

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

                if(n % i == 0) {
                    isPrime = false;
                    break;
                }

            }

        }

        if(isPrime)
            cout << n << " ";

    }

    cout << endl;

    return 0;

}

In this program, we loop through each number in the range and assume it is prime at the start. Then we check all numbers from 2 up to one less than the number itself. If any number divides evenly, we mark it as non-prime. This method is easy to understand and is ideal for beginners learning how loops and conditional statements work together.

Program 2: Optimized Method Using Square Root

Checking all numbers up to n-1 is unnecessary. We can optimize the program by checking divisibility only up to the square root of each number, reducing computation significantly.

#include <iostream>
#include <cmath>

using namespace std;

int main() {

    int start, end;

    cout << "Enter the range (start and end): " << endl;
    cin >> start >> end;

    for(int n = start; n <= end; n++) {

        bool isPrime = true;
        if(n <= 1) isPrime = false;

        else {

            double limit = sqrt(n);

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

                if(n % i == 0) {
                    isPrime = false;
                    break;
                }

            }

        }

        if(isPrime)
            cout << n << " ";

    }

    cout << endl;

    return 0;

}

Using the square root optimization reduces the number of iterations needed to check each number. Any factor larger than the square root has a corresponding smaller factor, so it’s unnecessary to check beyond the square root. Beginners can see how a small mathematical insight can improve efficiency while keeping the code readable.

Program 3: Using a Custom Function

Encapsulating the prime check in a function makes the code reusable and modular. This approach is useful when you want to print prime numbers for multiple ranges or reuse the prime-checking logic elsewhere.

#include <iostream>
#include <cmath>

using namespace std;

bool isPrime(int n) {

    if(n <= 1) return false;

    double limit = sqrt(n);

    for(int i = 2; i <= limit; i++) {
        if(n % i == 0) return false;
    }

    return true;

}

int main() {

    int start, end;

    cout << "Enter the range (start and end): " << endl;
    cin >> start >> end;

    for(int n = start; n <= end; n++) {

        if(isPrime(n))
            cout << n << " ";

    }

    cout << endl;

    return 0;

}

Here, the isPrime() function checks whether a number is prime, and the main loop prints all prime numbers in the range. Using functions makes the code cleaner and helps beginners practice modular programming, allowing the same logic to be reused easily.

Program 4: 6k ± 1 Optimization

For numbers greater than 3, all prime numbers are of the form 6k ± 1. This insight allows us to skip multiples of 2 and 3, reducing unnecessary checks and improving performance for moderately large ranges.

#include <iostream>
#include <cmath>

using namespace std;

bool isPrime6k(int n) {

    if(n <= 1) return false;
    if(n <= 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false;

    int limit = sqrt(n);

    for(int i = 5; i <= limit; i += 6) {

        if(n % i == 0 || n % (i + 2) == 0)
            return false;

    }

    return true;

}

int main() {

    int start, end;

    cout << "Enter the range (start and end): " << endl;
    cin >> start >> end;

    for(int n = start; n <= end; n++) {

        if(isPrime6k(n))
            cout << n << " ";

    }

    cout << endl;

    return 0;

}

This program checks numbers using the 6k ± 1 pattern, which skips obvious non-prime candidates. By iterating in steps of 6 and checking only i and i+2, we reduce the number of iterations compared to the square root method. Beginners can see how simple mathematical observations can make programs more efficient without complicating the code.

Program 5: Using the Sieve of Eratosthenes

For printing all prime numbers in a large range, the Sieve of Eratosthenes is highly efficient. It systematically marks multiples of each prime, leaving only the prime numbers unmarked. This method is faster than checking each number individually and is ideal for ranges with hundreds or thousands of numbers.

#include <iostream>
#include <vector>

using namespace std;

int main() {

    int start, end;

    cout << "Enter the range (start and end): " << endl;
    cin >> start >> end;

    if(end < 2) {

        cout << "No prime numbers in this range." << endl;
        return 0;

    }

    vector<bool> isPrime(end + 1, true);
    isPrime[0] = isPrime[1] = false;

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

        if(isPrime[i]) {

            for(int j = i*i; j <= end; j += i)
                isPrime[j] = false;

        }

    }

    for(int n = start; n <= end; n++) {

        if(isPrime[n])
            cout << n << " ";

    }

    cout << endl;

    return 0;

}

The Sieve of Eratosthenes efficiently finds all primes up to a given limit. Instead of checking each number, it marks multiples of primes as non-prime. Beginners can learn how array-based techniques and nested loops can optimize number-theory tasks, preparing them for more advanced algorithms.

Frequently Asked Questions (FAQ)

Here are some common questions beginners ask about printing prime numbers in a range:

Q1: Can 1 be a prime number?
No, 1 is not prime because it only has one divisor.

Q2: Why check up to the square root of a number?
Any factor larger than the square root would have a corresponding smaller factor, so checking beyond the square root is unnecessary and slows the program.

Q3: What is the 6k ± 1 method?
For numbers greater than 3, all prime numbers are of the form 6k ± 1. This allows skipping multiples of 2 and 3, reducing unnecessary checks for moderately large ranges.

Q4: When should I use the Sieve of Eratosthenes?
The sieve is best for large ranges because it efficiently marks non-primes in a batch rather than checking each number individually. It is ideal for hundreds or thousands of numbers.

Q5: Can I reuse a prime-checking function?
Yes, creating a function to check if a number is prime makes your code modular, allowing it to be reused across multiple programs or ranges.

Conclusion

Printing prime numbers in a range in C++ combines important programming concepts like loops, conditionals, arrays, and functions. We explored five approaches: a basic loop method, an optimized square root method, a reusable function, the 6k ± 1 optimization, and the Sieve of Eratosthenes. Beginners should start with simple loops to understand the logic, then move to square root or 6k ± 1 methods for moderately large ranges. For very large ranges, the Sieve of Eratosthenes provides the most efficient solution. By practicing these methods, beginners can strengthen both their programming skills and their understanding of prime numbers, preparing them for more advanced algorithmic challenges.

Additional & References

Exploring prime numbers in ranges is foundational for learning algorithms, cryptography, and mathematical programming. Beginners are encouraged to try larger ranges, experiment with optimizations, and explore sieve-based algorithms for efficiency.

Related Posts

Scroll to Top