发现相邻的奇数只能恰好差 \(2\)(偶质数只有 \(2\))。
而大于 \(3\) 的三个连续奇数至多有两个是质数,因为有一个能被 \(3\) 整除。对于 3 5 7
这三个数,我们可以构造成 3 5 2 7
以归入下面的构造方法。
所以相邻的奇数最多只有两个。
但我们可以放偶质数 \(2\)。显然,放多个 \(2\) 肯定不优。
于是我们就有 A A-2/A+2 2 B-2/B+2 B
这样的构造形式,根据情况可以省略部分。
这样就能过了,本着精益求精的精神我们继续探究。
拿 \(A\) 来讲,要存在合法的情况必须满足 \(A\) 是孪生质数中的一个。
假设 \(A\) 和 \(A-2\) 是质数,我们显然不需要构造一个 \(A-2\) 项因为 \(A\) 和 \(2\) 的差就是 \(A-2\)。
所以就可以少判断 \(A-2\) 这一项啦。
时间复杂度即为判断质数的复杂度。值得注意的是,除了 3 5 7
这种特殊情况,其余构造出来的解都是最短的。