c++ program to generate all the prime numbers between 1 and n
C++ program to generate all the prime numbers between 1 and n with explanations
#include <iostream>
#include <vector>
using namespace std;
void generatePrimes(int n) {
vector<bool> isPrime(n + 1, true);
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * 2; i <= n; i += p) {
isPrime[i] = false;
}
}
}
for (int p = 2; p <= n; p++) {
if (isPrime[p]) {
cout << p << " ";
}
}
}
int main() {
int n;
cout << "Enter the value of n: ";
cin >> n;
cout << "Prime numbers between 1 and " << n << " are: ";
generatePrimes(n);
return 0;
}
Explanation:
- We include the necessary header files to use input/output operations and vectors.
- We declare a function generatePrimes
that takes an integer n
as input.
- Inside the generatePrimes
function, we create a boolean vector isPrime
of size n + 1
and initialize all its elements to true.
- We then loop through the numbers starting from 2 up to the square root of n
.
- For each prime number p
, we mark all its multiples as non-prime in the isPrime
vector.
- Finally, we print all the prime numbers between 1 and n
by iterating through the isPrime
vector in the main
function.
This program efficiently generates all the prime numbers between 1 and n
using the Sieve of Eratosthenes algorithm.