Problem Statement

You are given an integer n. You need to find out the number of prime numbers in the range [1, n] (inclusive). Return the number of prime numbers in the range.

A prime number is a number which has no divisors except, 1 and itself.

Examples

Example 1:

Input: n = 6
Output: 3

Explanation: Prime numbers in the range [1, 6] are 2, 3, 5.

Example 2:

Input: n = 17
Output: 7

Explanation: Prime numbers in the range [1, 15] are 2, 3, 5, 7, 11, 13, 17

Approaches

1️⃣ Brute Force Approach

Intuition:

A naive approach to count prime numbers till N, is to check every number starting from 1 till N for prime. Keep a counter to store the count. If the number is prime, increment the counter. Once all the numbers are checked, the counter stores the required count.

Approach:

1. Initialize a counter to store the count of prime numbers.
2. Iterate from 2 to n, and check the current value for prime (using the brute way). If found prime, increment the counter by 1.
3. After the iterations are over, the counter stores the required result.

Code:

class Solution {
public:

    // Function to check if the number is prime or not
    bool isPrime(int n) {
        // 1 or below 1 is not considered prime
        if (n < 1) {
            return false;
        }


		// if there is any divisor in between 2 and the number then it is prime.
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
             // its prime
                return false;
            }
        }
        // not prime.
        return true;
    }
    int primeUptoN(int n) {
        int count = 0;
       
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;

    }
};

Complexity Analysis:

• Time Complexity:O(N2) – Checking all numbers from 1 to n for prime and checking if a number is prime or not will take O(n) TC.
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.

2️⃣ Square Root (Optimized) Approach

Code:

class Solution {
public:
    bool isPrime(int n) {
        // 1 or below 1 is not considered prime
        if (n < 1) {
            return false;
        }

        for (int i = 2; i <= sqrt(n); ++i) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    int primeUptoN(int n) {
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;

    }
};

Complexity Analysis:

• Time Complexity:O(N3/2) – Checking all numbers from 1 to N for prime, will take O(N) and checking if a number is prime or not will take O(N1/2). Thus O(N*N1/2) = O(N3/2).
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.