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.