F. Sub-array Problem

★★★★★

3.1

9 votes

Details

Problem

Given an Array 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$ $K$ .

Constraints:

$1\leq N,K\leq 10^5$

$1\leq A[i]\leq 10^7$

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

Sub-arrays having $Primicity$ $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.