You have an array A of length N. You can perform an operation (you can perform the operation multiple times) on the elements of the array A. In the operation you can divide any element by its smallest factor greater than 1. You will be given Q tasks. In each task, you will be given an integer K and you have to tell the maximum number of elements in array A that can be reduced to 1 by using the operation at most K times.
Constraints:
\(1 \le N \le 10^6\)
\(1 \le Q \le 10^5\)
\(1 \le A_i \le 10^6\)
\(1 \le K \le 10^6\)
Input:
First line contains two space separated integers, N and Q.
Second line contains N space separated integers denoting the elements of the array A.
Next Q lines contains an integer each, denoting the value of K.
Output:
For each task, print the answer of the \(i^{th}\) task in a new line.
3 3 8 9 12 3 10 1
1 3 0
Number of operations required are \(3,2,3\) respectively.
For first task, we can reduce any one of the three elements to 1.
For second task, we can reduce all elements of the array to 1.
For third task, we cannot reduce any elements to 1.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor