Given an Array \(A\) of $$N$$ integers.You have to find number of subarrays having $$Primicity$$ less than or equal to $$K$$.
$$Primicity$$ of sub-array is defined an number of primes in that subarray.
Input:
First line contains \(N\) and \(K\).
Second line contains \(N\) integers.
Output:
Print the Number of sub-arrays having $$Primicity$$ \(\leq\)$$K$$.
Constraints:
\(1\leq N,K\leq 10^5\)
\(1\leq A[i]\leq 10^7\)
5 1 2 3 4 5 9
9
Sub-arrays having $$Primicity$$ \(\leq\) $$K$$ are:-
\([1,1],[2,2],[2,3],[3,3],[3,4],[4,4],[3,5],[4,5],[5,5].\)
\([l,r] \) here \(l,r\) are indices.
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
No editorial available for this problem.
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