Matriz prima


Submit solution


Points: 100 (partial)
Time limit: 4.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

Usted tiene una matriz \(n × m\). La matriz consta de números enteros. En un movimiento, puede aplicar una transformación a la matriz: elija un elemento arbitrario de la matriz y auméntelo en 1. Cada elemento puede aumentarse un número arbitrario de veces.

Tiene mucha curiosidad por los números primos. Permítanos recordarle que un número primo es un entero positivo que tiene exactamente dos divisores enteros positivos distintos: él mismo y el número uno. Por ejemplo, los números 2, 3, 5 son primos y los números 1, 4, 6 no lo son.

Una matriz es prima si se cumple al menos una de las dos condiciones siguientes:

  • la matriz tiene al menos una fila que solo contiene números primos;
  • la matriz tiene al menos una columna que solo contiene números primos;

Su tarea es contar el número mínimo de movimientos necesarios para obtener una matriz prima a partir de la que tiene.

Entrada

La primera línea contiene dos números enteros n, m (1 \le n, m \le 500) - el número de filas y columnas en la matriz, correspondientemente.

Cada una de las siguientes n líneas contiene m enteros: la matriz inicial. Se cumple que 1 \leq A_{ij} \leq 10^5 para todo 1 \leq i \leq n y 1 \leq j \leq m.

Los números de las líneas están separados por espacios simples.

Salida

Imprima un solo entero: el número mínimo de movimientos necesarios para obtener una matriz prima a partir de la que tiene. Si tiene una matriz prima, imprima 0.

Puntuación

  • Subtarea 1 (30 ptos): M = 1, A_{ij} \leq 1000.
  • Subtarea 2 (70 ptos): Sin restricciones adicionales

Ejemplos

Ejemplo de entrada 1
3 3
1 2 3
5 6 1
4 4 1
Ejemplo de salida 1
1
Ejemplo de entrada 2
2 3
4 8 8
9 2 9
Ejemplo de salida 2
3
Ejemplo de entrada 3
2 2
1 3
4 2
Ejemplo de salida 3
0

Nota

En la primera muestra, debe aumentar el número 1 en la celda (1, 1). Así, la primera fila estará formada por números primos: 2, 2, 3.

En la segunda muestra, debe aumentar el número 8 en la celda (1, 2) tres veces. Así, la segunda columna estará formada por números primos: 11, 2.

En la tercera muestra no tiene que hacer nada ya que la segunda columna ya consta de números primos: 3, 2.


Comments

There are no comments at the moment.