SWPU第二届天梯选拔赛暨蓝桥杯训练赛题解

视频讲解

https://www.bilibili.com/video/BV1kL4y1T7mm

比赛链接

http://acm.mangata.ltd/contest/622ed21757358147cbd2ab4a

赛况

距离比赛还有十分钟的截图，我校排在前面的基本没有，看得出来有人寒假摆烂了，整体的题目难度不算难，前五题基本不包括什么算法，完全是仿照天梯赛的L1、L2出题的，然后后两题是对标的L3，自认为此套题目是有一定区分度的，有人AK，大部分人签到成功。

过题数(>=x)人数112621023704505236871

希望赛后同学们能积极补题吧，奋战一个月后的天梯赛

A.素数送温暖（暴力） 思路

我们直接写一个暴力的素数判断，复杂度为 O ( ( x ) ) O(\sqrt(x)) O(( ​x)) ，又由于在 1 0 9 10^9 109 以内的两个素数间隔是 282 282 282 于是我们至多进行常数次判断复杂度为 O ( ( x ) ) O(\sqrt(x)) O(( ​x))

代码

#include
using namespace std;

bool is_prime(int x){
	if(x == 0 || x == 1) return false;
	for(int i = 2;i * i >x;
	for(int i = x + 1;true; ++i) {
		if(is_prime(i)) {
			cout