# Find all Prime Numbers less than equal to N | Set 1

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:

1. Iterate through 0 to N and check if the number is prime, if yes then print it.
1. 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.

Time Complexity: O(N2

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.