CF271B.Prime Matrix

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You've got an $n×m$ matrix. The matrix consists of integers. In one move, you can apply a single transformation to the matrix: choose an arbitrary element of the matrix and increase it by $1$ . Each element can be increased an arbitrary number of times.

You are really curious about prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors: itself and number one. For example, numbers 2, 3, 5 are prime and numbers 1, 4, 6 are not.

A matrix is prime if at least one of the two following conditions fulfills:

the matrix has a row with prime numbers only;
the matrix has a column with prime numbers only;

Your task is to count the minimum number of moves needed to get a prime matrix from the one you've got.

输入格式

The first line contains two integers $n,m$ $(1<=n,m<=500)$ — the number of rows and columns in the matrix, correspondingly.

Each of the following $n$ lines contains $m$ integers — the initial matrix. All matrix elements are positive integers. All numbers in the initial matrix do not exceed $10^{5}$ .

The numbers in the lines are separated by single spaces.

输出格式

Print a single integer — the minimum number of moves needed to get a prime matrix from the one you've got. If you've got a prime matrix, print 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
```

说明/提示

In the first sample you need to increase number 1 in cell (1, 1). Thus, the first row will consist of prime numbers: 2, 2, 3.

In the second sample you need to increase number 8 in cell (1, 2) three times. Thus, the second column will consist of prime numbers: 11, 2.

In the third sample you don't have to do anything as the second column already consists of prime numbers: 3, 2.

首页