You have given a list of q queries and for every query, you are given an integer N. The task is to find how many numbers less than or equal to Nhave numbers of divisors exactly equal to3.
Example 1:
Input:
q = 1 query[0] = 6
Output:
1
Explanation:
There is only one number 4 which has exactly three divisors 1, 2 and 4 and less than equal to 6.
Example 2:
Input:
q = 2 query[0] = 6 query[1] = 10
Output:
1 2
Explanation:
For query 1 it is covered in the example 1. query 2: There are two numbers 4 and 9 having exactly 3 divisors and less than equal to 10.
Your Task:
You don't need to read input or print anything. Your task is to complete the functionthreeDivisors() which takes an integerq and a list of integer of sizeq as input parameter and returns the list containing the count of the numbers having exactly 3 divisors for each query.
Expected Time Complexity: O(NlogN),
Expected Auxiliary Space: O(N), where N is min(10^6,N)
Constraints :
1 <= q=""><=>3
1 <= query[i]=""><=>12
// { Driver Code Starts
//Initial Template for Java
import java.io.*;
import java.util.*;
class GFG
{
public static void main(String args[])throws IOException
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int q = sc.nextInt();
ArrayList query = new ArrayList<>();
for(int i=0;iquery.add(sc.nextLong());
}
Solution ob = new Solution();
ArrayList ans = ob.threeDivisors(query,q);
for(int cnt : ans) {
System.out.println(cnt);
}
}
}
}
// } Driver Code Ends
//User function Template for Java
class Solution{
static ArrayList threeDivisors(ArrayList query, int q){
// code here
}
}