Maximum Prime Count in Subarrays

You are given an array of integers and a positive integer K. Your task is to determine the maximum number of prime numbers found in any contiguous subarray (window) of size K.

Formally, given an array \( A = [a_1, a_2, \dots, a_n] \) and an integer \( K \) (with \( 1 \leq K \leq n \)), consider all subarrays of the form \( [a_i, a_{i+1}, \dots, a_{i+K-1}] \) for \( 1 \leq i \leq n-K+1 \). Let \( f(i) \) be the number of primes in the subarray starting at index \( i \). The goal is to compute:

$$\max_{1 \leq i \leq n-K+1} f(i)$$

If there are no primes in any window, output 0.

Examples:

• For K = 3 and arr = [1, 3, 7, 6, 13, 19, 18, 22], the answer is 2.
• For K = 2 and arr = [11, 15, 8, 5, 33, 7, 2], the answer is 2.
• For K = 1 and arr = [1, 3, 7, 6, 13, 19, 18, 22], the answer is 1.
• For K = 2 and arr = [4, 6, 8, 10], the answer is 0.
• For K = 2 and arr = [2, 3, 5, 7, 11, 13], the answer is 2.
• For K = 4 and arr = [7, 11, 3, 5, 2, 1, 17, 19], the answer is 4.

inputFormat

The input is given via stdin in the following format:

K
N
a1 a2 a3 ... aN

where:

• K is the size of the window.
• N is the number of elements in the array.
• a1, a2, ..., aN are the elements of the array, separated by spaces.

outputFormat

Output a single integer on stdout representing the maximum number of prime numbers in any contiguous subarray of size K.

## sample

3
8
1 3 7 6 13 19 18 22

2

</p>