Nested Control Structures in C++: Finding Prime Numbers in a Range
-
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.
-
@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; }
-
@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.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?