All Prime Numbers less than or equal to N

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
7 upvotes
Asked in companies
AccentureSliceHCL Technologies

Problem statement

You are given a positive integer 'N'. Your task is to return all the prime numbers less than or equal to the 'N'.

Note:

1) A prime number is a number that has only two factors: 1 and the number itself.

2) 1 is not a prime number.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow. 

The first line of each test case contains only one integer 'N', as described in the problem statement.
Output Format: 
For each test case, return a sequence of integers denoting the prime number less than or equal to 'N' in the increasing order.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
2 <= N <= 5000

Time Limit: 1sec
Sample Input 1:
1
5
Sample Output 1:
2 3 5
Explanation for sample input 1:
2,3 and 5 are the only prime numbers less than or equal to 5.
Sample Input 2:
1
8
Sample Output 2:
2 3 5 7
Explanation for sample input 2:
2,3,5 and 7 are the only prime numbers less than or equal to 8.
Hint

Think of the Brute Force approach.

Approaches (3)
Brute Force Approach

The idea here is to check every number less than or equal to N is prime or not. Those who are prime just add them in an array and return the array at the end of the function.

 

  • Create an empty array named as 'RESULT' to store the prime numbers.
  • Run a loop with variable ‘i’ from 2 to ‘N’ and in each iteration do:
    • Check whether ‘i’ is prime or not, call the function 'IS_PRIME'(i), which has a return type bool. It returns true if ‘i' is a prime number, else it returns false.
    • If 'IS_PRIME'(i) == true, then add i to the 'RESULT' array.
  • Return the 'RESULT' array.

bool 'IS_PRIME'(int n):

  • This function is checking whether the number ‘N’ is prime or not.
  • Run a loop with a variable ‘i’ from 2 to N-1 because if ‘N’ is prime, then it is not having any divisors in the range [2, N-1] :
    • If ‘N’ % ‘i’ == 0, which implies that i is a divisor of ‘N’, so simply return false.
  • If the above loop is completed, then that it is guaranteed that ‘N’ is a prime number, so return true.
Time Complexity

O(N^2), where ‘N’ is the number given in the problem.

 

We are checking for each number in the range 2 to ‘N', and for each number, we are further running a loop till ‘N-1’ to check whether it is prime or not. So, we are using a nested loop which gives a time complexity of O(N^2).

Space Complexity

O(N), where ‘N’ is the number given in the problem.

 

Although the size of the result array is equal to the number of prime numbers less than or equal to ‘N’, this value increase as the ‘N’ value increases. So, we can mention it as O(N).

Code Solution
(100% EXP penalty)
All Prime Numbers less than or equal to N
Full screen
Console