本题要求用“只包含 1 和合数”的数组凑出给定整数 n,并使数组长度最短(长度至少为 2)。 做法属于构造 + 数论 + 贪心:为了最短,优先尝试用 2 个数完成(因为长度不能为 1)。若不能,再用 3 个或更多。
关键观察(合数定义:大于 1 且有除 1 和自身外的正因子):
给定一个正整数 n 。请你找到一个长度至少为 2 的数组 a ,使得数组 a 中仅含 1 和合数(可以只包含 1,可以只包含合数,也可以同时有合数和 1 ),且 a 中所有元素的和为 n 。如果有多个满足条件的 a ,请输出长度最短的。如果有多个长度最短的 a ,你可以输出任意一个。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
【名词解释】