Be the first user to complete this post

  • 0
 Add to List
Beginner

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: 

  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) 

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.

Related Problems: