Problem Statement

You are given an integer n. Print all the prime numbers till n (including n).

A prime number is a number greater than 1 that is divisible only by 1 and itself.

Examples

Example 1:

Input: n = 7
Output: [2, 3, 5, 7]

Explanation:
The number 2 has only two divisors 1 ans 2.
The number 3 has only two divisors 1 and 3.
The number 5 has only two divisors 1 and 5.
The number 7 has only two divisors 1 and 7.

Example 2:

Input: n = 2
Output: [2]

Explanation: There is only one number 2 that is a prime till 2.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

A naive approach to print all prime numbers till N, is to check every number starting from 1 till N for prime. If the number is prime, it can be stored in a list. Once all the numbers are checked, the counter stores the required count.

Approach:

1. Declare a list to store all the primes till N.
2. Iterate from 2 to N, and check the current value for prime (using the optimal way). If found prime, store it in a list.
3. After the iterations are over, all the prime numbers are stored in the list.

Code:

// Example program to find and print all prime numbers up to a given number

#include <iostream>
#include <vector>
using namespace std;

// Function to check if a number is prime
bool isPrime(int num) {
    // A prime number is greater than 1 and has no divisors other than 1 and itself
    // We check if num is divisible by any number from 2 to num-1
    for (int i = 2; i < num; i++) {
        if (num % i == 0) return false; // If divisible, it's not prime
    }
    return true; // If not divisible by any number, it's prime
}

int main()
{
    int num = 10; // Set the upper limit. We want to find primes up to 10.
    
    vector<int> result; // Vector to store all prime numbers we find

    // Loop through all numbers from 2 to num
    for (int i = 2; i <= num; i++) {
        // If i is a prime number, add it to the result vector
        if (isPrime(i)) {
            result.push_back(i);
        }
    }

    // Print all prime numbers found
    for (int elm : result) {
        cout << elm << endl;
    }
}

Complexity Analysis:

• Time Complexity:O(n^2)
  • As for each number we are checking if it is divisible from 2 to number itself.
  • So there are two nested loops.
• Space Complexity:O(1)

2️⃣ Better Approach

Intuition:

If we look at the function isPrime, we can optimize it, as we are looping from the 2 to the number itself. In fact we should loop from the 2 to sqrt(num), as there will be no divider of number num greater than its square root.

Approach:

• In the isPrime() function just change the loop range from 2 to sqrt(num)

Code:

// Program to print all prime numbers up to a given number using sqrt optimization

#include <iostream>   // For input/output operations
#include <vector>     // For using the vector container
#include <cmath>      // For using the sqrt() function
using namespace std;

// Function to check if a number is prime
bool isPrime(int num) {
    // Numbers less than 2 are not prime
    if (num < 2) return false;

    // Check for divisibility from 2 up to the square root of the number
    // If any number divides 'num', it's not prime
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false;
    }

    // If no divisor found, the number is prime
    return true;
}

int main() {
    int num = 10; // The upper limit up to which we want to find prime numbers

    vector<int> result; // Vector to store all prime numbers found

    // Loop through all numbers from 2 to 'num'
    for (int i = 2; i <= num; i++) {
        // Check if the current number is prime
        if (isPrime(i)) {
            // If it is prime, add it to the result vector
            result.push_back(i);
        }
    }

    // Print all the prime numbers stored in the result vector
    for (int elm : result) {
        cout << elm << endl;
    }
}

Complexity Analysis:

• Time Complexity:O(n sqrt(n))
  • The outer loops runs n times
  • The inner loops runs for under root(n) times
• Space Complexity:O(1)
  • Constant space

3️⃣ Sieve of Eratosthenes

Intuition:

The Sieve of Eratosthenes is an efficient way to find all prime numbers up to a given number n.

Instead of checking each number one by one to see if it's prime (slow), we eliminate multiple of every prime number in a smart way. Think of it like marking off non-primes (composites) in a list.

Approach:

1. Assume all numbers from 2 to n are prime.
2. Start from the first prime number 2.
3. Mark all multiples of 2 are not prime.
4. Move to the next number that is still marked as prime and repeat.
5. Continue this process up to √n.
6. At the end, the numbers still marked true are prime.

Code:

#include <iostream>
#include <vector>
using namespace std;

// Function to find all prime numbers up to 'num' using the Sieve of Eratosthenes
void sieve(int num) {
    // Step 1: Create a boolean array 'isPrime' of size num+1
    // Initially assume all numbers are prime (true)
    vector<bool> isPrime(num + 1, true);

    // 0 and 1 are not prime numbers
    isPrime[0] = isPrime[1] = false;

    // Step 2: Start from the first prime number (2) and eliminate its multiples
    // Only go up to sqrt(num) for efficiency
    for (int i = 2; i * i <= num; i++) {
        // If 'i' is still marked as prime
        if (isPrime[i]) {
            // Mark all multiples of 'i' as not prime
            // Start from i*i (because smaller multiples were already marked)
            for (int j = i * i; j <= num; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // Step 3: Print all numbers that are still marked as prime
    for (int i = 2; i <= num; i++) {
        if (isPrime[i]) {
            cout << i << endl;
        }
    }
}

int main() {
    int num = 10; // Change this value to find primes up to a different number

    // Call the sieve function
    sieve(num);

    return 0;
}

Complexity Analysis:

• Time Complexity:O(n log log n)
• Space Complexity:O(n)