All Prime Numbers less than or equal to N

Posted: 3 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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.
Try Problem