**Objective:** Given a number N, Write a program to find all prime numbers which are between 0 and N.

**Prime Number :** A prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself.

**Example:**

N = 10 Output: 2 3 5 7 N = 60 Output: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59

**Naive Approach: **

- Iterate through 0 to N and check if the number is prime, if yes then print it.
- To check if any number
**x**is prime, check if**x**is a multiple of any number between**2**and**x**, if yes then the number is not a prime number.

- To check if any number

**Time Complexity: O(N**^{2}**) **

**Complete Code:**

**Output:**

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

**Better Approach:**

To validate whether any given number **x** is prime or not, actually, we do not need to check for all the numbers between 2 and x. we can actually check if **x** is a multiple of any number between **2** and sqrt(x), if yes then the number is not a prime number.

**Time Complexity: O(N Sqrt(N))**

**Complete Code:**

**Output**:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

We can further optimize this using Sieve of Eratosthenes. Click to read about it more.