Máximo divisor primo común.


Submit solution

Points: 40 (partial)
Time limit: 3.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++, Pascal, Python, VB

Recientemente, uno de los informáticos de la IslaInformatiza aprendió a encontrar el máximo común divisor de dos o más números, pero nunca se dió cuenta de que el 1 no es un número primo. Ahora quiere saber cuál es el mayor divisor primo común de dos o más números. El cree que el máximo divisor primo común de dos o más números es el primo más grande que divide cada uno de los números sin dejar resto, 1 si no lo hay (el informático piensa que 1 es un número primo).

El informático ha escrito una fila de N números primos positivos y mira todas las secuencias de números consecutivos de longitud K. Para cada una de estas secuencias existe un máximo primo que divide cada uno de los números (le llamaremos NOPD). El quiere saber quién es el más grande de todos.

Escribe un programa que, dados N, K y una secuencia de N números, determine el máximo valor de NOPD de todas las secuencias (subarreglos) de longitud K.

Entrada

La primera línea contiene los dos números enteros N y K. La segunda línea contiene N enteros, los elementos de la fila.

Salida

Genere un único número entero: la respuesta deseada.

Restricciones

  • 2 \leq K \leq N \leq 10^6.
  • Los números de la fila no superan 10^6.

Ejemplo #1 de Entrada

7 3
18 6 12 20 30 20 7

Ejemplo #1 de Salida

5

Explicación del ejemplo: Todas las secuencias de longitud 3 son:

{18, 6, 12}, 
{6, 12, 20}, 
{12, 20, 30}, 
{20, 30, 20} y 
{30, 20, 7}.

Sus respectivos NOPD son: 3, 2, 2, 5 y 1. El valor máximo es 5.

Ejemplo #2 de Entrada

4 2
3 14 25 8
Ejemplo #2 de salida
1

Comments

There are no comments at the moment.