Last Updated: 29 Oct, 2020

Find prime numbers

Easy

Asked in companies

Solve now

Problem statement

You are given a positive integer ‘N’. Your task is to print all prime numbers less than or equal to N.

Note: A prime number is a natural number that is divisible only by 1 and itself. Example - 2, 3, 17, etc.

You can assume that the value of N will always be greater than 1. So, the answer will always exist.

Input Format:

The input contains a single positive integer ‘N’.

Output Format :

Print single space-separated prime numbers less than or equal to ‘N’ in increasing order.

Note :
You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

2 <= N <= 10^7

Where ‘N’ is the given positive integer.

Time Limit: 1sec

Solve now

Approaches

01 Approach

We use Brute Force to solve this problem.

We iterate from 2 to N.
For each number num, we check if it is prime or not. We use the following approach to check if a given number is prime.
1. We loop through all numbers from 2 to num - 1.
2. For every number in the loop, we check if it divides num.
3. If we find any number that divides num, we can say num is not prime.
4. If num is prime, we store it in the result vector/list.
Finally, we return the result vector/list.

Solve now

02 Approach

We will optimize the test to check if a given number is prime. Instead of looping to N-1, we check divisibility till (N)^½. This is because if the number is not prime, there must be at least one divisor till N^½.

Now, we use the brute force approach along with an optimized primality test.

We iterate from 2 to N.
For each number num, we check if it is prime or not. We use the following optimized approach to check if a given number is prime.
1. We loop through all numbers from 2 to (num)^½.
2. For every number in the loop, we check if it divides num.
3. If we find any number that divides num, we can say num is not prime.
4. If num is prime, we store it in the result vector/list.
Finally, we return the result vector/list.

Solve now

03 Approach

We will use the Sieve of Eratosthenes to solve this problem.

First, we will make a boolean array/list isPrime of size N + 1. This will mark if a number is prime or not. Initially, all values will be true.
Then, we initialize a variable num equal to 2 which represents the current processing prime number.
We will loop as num from 2 to N^½:
1. If num is not prime, we continue.
2. Else, we will mark all multiples of num in isPrime as false.
In the end, we will iterate through isPrime and store all primes in the result vector/list.
Finally, we return the result vector/list.

Solve now