文章

20

粉丝

146

获赞

10

访问

41.6k

头像
解题思路:注意观察数据范围
P1876 清华大学2021年机试题
发布于2023年3月17日 18:02
阅读数 1.9k

这道题的关键是数据范围,给的数字最大是100,所以这个题可以很简单的做。

我们打个素数表可以发现,除了20,32,51,53,62,84,89这几个数以外的所有数都可以直接在后面加一位一定有一个是质数。

这几位在后面加两位也能构成至少一个质数。

所以我们直接对于给定的数X,要加的数从1开始枚举到99,判断X1,X2,X3.....X99这些数是否是素数。

最先出现的就是最小的。

时间复杂度是 100 * 判断是否素数,判断素数的复杂度可以是sqrt(n)

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发