模具份数凑公约

题目内容

烘焙间里摆着一排装袋模具，从左到右第 $i$ 个模具里已有 $pieces[i]$ 块饼干（$i$ 从 $0$ 开始）。值班师傅希望能挑出两个不同模具，使它们的饼干数存在大于 $1$ 的公因数，这样就能按同一份数规格去分装。

允许的操作是：选中某一个模具，往里面再放 $1$ 块饼干。每次操作代价记为 $1$，可以操作任意多次（也可以一次都不做）。

请计算：最少需要多少次操作，才能让数组里存在两个下标 $i \neq j$，满足 $\gcd(pieces[i], pieces[j]) > 1$。

请实现：

minShareOps(pieces: int[]) -> int

输入描述

一行整型数组，形如 $[1, 1]$。

约束：

• $2 \le pieces.length \le 200000$
• $1 \le pieces[i] \le 200000$

输出描述

一行整数：最少操作次数。

样例1

输入：

[1, 1]

输出：

2

说明：

• 初始 $\gcd(1,1)=1$，不满足
• 可以把两个模具各加 $1$ 次，变成 $[2, 2]$，$\gcd=2$
• 可以证明 $2$ 次是最少

样例2

输入：

[4, 8]

输出：

0

说明：已有 $\gcd(4,8)=4>1$，无需操作。

样例3

输入：

[3, 11]

输出：

1

说明：把 $3$ 加一次变成 $4$ 后，$\gcd(4,11)=1$ 仍不行；但把 $11$ 加一次变成 $12$，$\gcd(3,12)=3>1$，代价为 $1$。