Find prime numbers
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

Question

Find prime numbers

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1), constant space is used.

Time Complexity: O(1)Explanation:

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).

Accepted Answer

Optimized primality test

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.

Space Complexity: O(1)Explanation:

O(1), constant space is used.

Time Complexity: O(1)Explanation:

O(N^3/2), where N is the given positive integer.

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

Accepted Answer

Sieve of Eratosthenes

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.

Space Complexity: O(1)Explanation:

O(N), where N is the given positive integer.

We create a boolean array/list isPrime to store all numbers from 2 to N.

So, the space complexity is O(N).

Time Complexity: O(1)Explanation:

O(N * log(log N)) where N is the given positive integer.

The algorithm will perform N / p operations for every prime p ≤ N in the inner loop. So, the number of times the loop runs is equal to ΣN/p = N* Σ1/p where p ≤ N.

The value of Σ1/p is log(log N). So, the overall time complexity is O(N *log(log N)).

For a detailed explanation, visit here.

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:

Output Format :

Constraints:

Top PayU Payments Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in PayU Payments Software Developer