← 返回题目列表

Codeforces · 271/B

B. 素数矩阵

中文机器翻译题面 查看原题

你有一个 n × m 矩阵。该矩阵由整数组成。您可以一次性对矩阵应用一次变换:选择矩阵的任意元素并将其加 1。每个元素都可以增加任意次数。

你真的对素数很好奇。让我们提醒您,素数是一个正整数,它恰好有两个不同的正整数除数:它本身和数字一。例如,数字 2、3、5 是质数,而数字 1、4、6 则不是。

如果至少满足以下两个条件之一,则矩阵是素数:

- 矩阵有一行仅包含素数;
- 矩阵有一列仅包含素数;

你的任务是计算从你现有的矩阵中获得质数矩阵所需的最少移动次数。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 500) — 相应地,矩阵中的行数和列数。

以下 n 行中的每一行都包含 m 个整数 — 初始矩阵。所有矩阵元素均为正整数。初始矩阵中的所有数字不超过105。

行中的数字由单个空格分隔。

输出

打印一个整数——从已有的矩阵中获得素数矩阵所需的最少移动次数。如果你有素矩阵,则打印 0。

示例

输入 #1

3 3
1 2 3
5 6 1
4 4 1

输出 #1

1

输入 #2

2 3
4 8 8
9 2 9

输出 #2

3

输入 #3

2 2
1 3
4 2

输出 #3

0

注意

在第一个示例中,您需要增加单元格 (1, 1) 中的数字 1。因此,第一行将包含素数:2、2、3。

在第二个示例中,您需要将单元格 (1, 2) 中的数字 8 添加三次。因此,第二列将由素数组成:11、2。

在第三个示例中,您无需执行任何操作,因为第二列已经包含素数:3、2。