Last Updated: 4 Jan, 2021

3 Divisors

Moderate

Asked in companies

Solve now

Problem statement

You are given a positive integer ‘N’. Your task is to find all the positive integers between 1 and ‘N’ (both inclusive) that have exactly 3 divisors. Print these numbers in increasing order.

Note :

It is guaranteed that there is at least one such integer under given constraints.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and only line of each test case contains a positive integer ‘N’.

Output Format :

For each test case, print a single line consisting of space-separated integers between 1 and ‘n’ (both inclusive) in increasing order that has exactly 3 divisors.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
4 <= N <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Create a vector of integers ‘result’. It will store all the positive integers between 1 and ‘N’ (inclusive) which has exactly 3 divisors.
Run a loop where ‘i’ ranges from 1 to ‘N’ and for each ‘i’ check whether it has exactly 3 divisors or not. This can be done as follows.
- Initialize an integer variable ‘count’ = 0. It will store the number of divisors of ‘i’.
- Run a loop where ‘j’ ranges from 1 to square root of ‘i’. If for any ‘j’, ‘i’ is divisible by ‘j’ and the square of ‘j’ is not equal to ‘i’ then increment ‘count’ by 2 because it means it is divisible by both ‘j’ and ‘N / j’. Otherwise, if ‘i’ is divisible by ’j’ but the square of ‘j’ is equal to ‘i’ then increment ‘count’ by 1.
- If ‘count’ is equal to 3, then append ‘i’ in the vector result.
Return ‘result’

Solve now

02 Approach

We can show that only the square of prime numbers has exactly 3 divisors. This reduces our task to find all the prime numbers between 1 and sqrt(n). We will then print the square of these prime numbers. This can be done by using the Sieve of Eratosthenes as follows.

Create a boolean array ‘isPrime’ of size sqrt(n) and fill it with the boolean value ‘true’.
Run a loop where ‘i’ ranges from 2 to sqrt(n) and in each iteration do the following’.
- If ‘isPrime[i]’ is ‘true’ then run a loop where ‘j’ ranges from ‘i*i’ to ‘n’ and set ‘isPrime[j]’ to false, and then increment ‘j’ by ‘i’.
Create a vector of integers ‘result’. It will store all the positive integers between 1 and ‘n’ (inclusive) which has exactly 3 divisors.
Run a loop from ‘i’ ranges from 2 to sqrt(n), and for each ‘i’ if ‘isPrime[i]’ is ‘true’ then append square of ‘i’ in vector ‘result’.
Return ‘result’.

Solve now