3 Divisors

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in companies
OlaHashedIn

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5 
20
Sample Output 1 :
4
4 9
Explanation For Sample Input 1 :
Test case 1 :
There are exactly 3 divisors of 4, that is 1, 2, 4.
There is no other integer between 1 and 5 that has exactly three divisors.

Test case 2 :
There are exactly 3 divisors of 4, that is 1, 2, 4.
There are exactly 3 divisors of 9, that is 1, 3, 9.
There is no other integer between 1 and 20 that has exactly three divisors.
Sample Input 2 :
2
49
4
Sample Output 2 :
4 9 25 49
4
Hint

Count divisors of all the integers between 1 and ‘N’.

Approaches (2)
Brute Force
  • 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’
Time Complexity

O(N * sqrt(N)), where ‘N’ is the given positive integer.

 

It will take sqrt(N) time to count the number of divisors of the given number. We have to count the number of divisors for ‘N’ integers that make its complexity O(N * sqrt(N)).

Space Complexity

 O(M), where ‘M’ is the number of integers between ‘1’ and ‘N’ having exactly 3 divisors.

 

Space used by vector ‘result’ will be of the order ‘M’.

Code Solution
(100% EXP penalty)
3 Divisors
Full screen
Console