Nested Control Structures in C++: Finding Prime Numbers in a Range

[Sachin Bhatt]

I'm working on a C++ program to find prime numbers within a given range. I have a working implementation that uses nested control structures, but I'm wondering if there's a more efficient way to achieve this. Here's my code:

#include <iostream>

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

int main() {
    int lower, upper;
    std::cout << "Enter the lower and upper bounds: ";
    std::cin >> lower >> upper;
    
    std::cout << "Prime numbers in the range " << lower << " to " << upper << " are: ";
    for (int i = lower; i <= upper; ++i) {
        if (isPrime(i)) {
            std::cout << i << " ";
        }
    }
    return 0;
}

I'm wondering whether there's a more effective or beautiful approach to discovering prime numbers in a particular range without utilizing nested control structures than the code I've written, even if it still works. I've checked several websites like Scaler on the internet, but I haven't found a good answer. Any advice or fresh ideas would be highly appreciated. I want to make my code efficient without sacrificing readability or precision.

[J.Hilk]

@Sachin-Bhatt you should be able to get away with this reduced loop:

for (int i = 5; i <= std::sqrt(n); i += 6) {

I'm wondering whether there's a more effective or beautiful approach to discovering prime numbers in a particular range without utilizing nested control structures than the code I've written, even if it still works.

ChatGPT suggests the Sieve of Eratosthenes algorithm:

#include <iostream>
#include <vector>

std::vector<int> sieve_of_eratosthenes(int n) {
    std::vector<bool> primes(n+1, true);
    primes[0] = primes[1] = false;
    for (int p = 2; p*p <= n; p++) {
        if (primes[p] == true) {
            for (int i = p*p; i <= n; i += p)
                primes[i] = false;
        }
    }
    std::vector<int> prime_numbers;
    for (int p = 2; p <= n; p++)
        if (primes[p])
            prime_numbers.push_back(p);
    return prime_numbers;
}

int main() {
    int lower = 10;
    int upper = 50;
    std::vector<int> prime_numbers = sieve_of_eratosthenes(upper);
    std::cout << "Prime numbers in the range " << lower << " to " << upper << " are:\n";
    for (int num : prime_numbers) {
        if (num >= lower)
            std::cout << num << "\n";
    }
    return 0;
}

[JonB]

@J-Hilk
One difference to be aware of is that Eratosthenes or similar uses storage (primes[]) for its computation where the OP's does not. This might become costly if upper bound is large? I refused to use this approach on my computations of primes into the 100s of billions for this reason! I picked a compromise where I store all the primes as I calculate them for future re-use, but not maintain an array holding true/false for every number in the range.

@Sachin-Bhatt

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }

I do not recall coming across this approach/algorithm/equation. Can you provide a reference link, please?

I wonder how it compares against my way of storing all the previous primes and doing a MOD using just them? You visit every number in steps of 6 and do 2 MODs. That is still a lot of numbers to visit if n is into the trillions?