Be the first user to complete this post

Add to List 
374. 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:
 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.
Time Complexity: O(N^{2})
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))
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.