Find prime numbers

Easy

0/40

Average time to solve is 15m

52 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1 :

2 3 5 7

Sample Output 1 Explanation:

For the given input, all prime numbers from 2 to 7 are 2, 3, 5 and 7.

Sample Input 2 :

Sample Output 2 :

2 3 5 7 11 13 17 19 23 29

Hint 1

Hint 2

Hint 3

Naively check for all prime numbers from 2 to N.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute force 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.

Time Complexity

O(N^2), where N denotes the given positive integer.

We loop from 2 to N and for each number NUM, we loop from 2 to NUM - 1 to check if the given number is prime. So, the overall time complexity is O(N^2).

Space Complexity

O(1), constant space is used.

(100% EXP penalty)

Find prime numbers

Console