Problem Statement

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

A prime number is a number that has only two divisor's 1 and the number 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.