周梦晗试题分析（三）-HelloWorld少儿编程
周梦晗试题分析（三）-HelloWorld少儿编程
周梦晗
在分析试题三之前，我们先来完善下试题二的程序，上篇文章发布之后，有小伙伴和小编说程序不严谨呢，之前的程序只是判断最终的结果()数量是否匹配，但在输入的过程中右括号）的数量超过左括号（，则说明括号不匹配。
程序稍微修改即可满足所有情况，小编也非常感谢各位小伙伴的提醒及参与，完善后的程序如下。小伙们如果有更好的解决方法也可以后台回复小编哦。
Part 3
试题三分析
第三题题目是《和素数》。想要正确完成本题，了解素数的概念并能编写程序判断一个自然数是不是素数显得至关重要。首先，我们来回顾一下题目吧。
第三题:和素数
小李作为志愿者，应聘担任学校图书馆助理馆长，有一堆书要他整理，每本书都有一个书号（<=200000)，现在他有一本书，这本书的书号为K（<=200000),现在他要找出一本书号比这本书大的书和书号比这本小的书(但都要书号最接近已有的书号K），将找到的这两本书的书号加起来，并计算加起来以后的数是否为素数
【输入格式】
第一行二个自然数N,K，表示几本书以及已有书的书号（<=200000) 第二行开始有N个整数，表示这些书的书号
【输出格式】
第一行一个数，表示两本书书号加起来的和 第二行一个字符，表示和是否为素数，若是则输出"Y"否则输出"F"（引号不打出）
【输入输出样例】
输入：
6 16
14 5 3 1 17 20
输出：
31
Y
题目网站链接：
样/例/说/明
14、5、3、1、17、20六个书号中最接近书号K（=16）的书号为14和17，它们的和为31，是素数，则输出Y。
首先了解素数的定义，一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，这样的自然数叫作素数（或质数）。
举个例子，2，3，5，11这些只能被1和本身整除的自然数都是素数。
4，9，10，12这些自然数，除了1和本身之外还有其他约数，所以它们都不是素数。
判断一个自然数n是否是素数，有两种常用方法：
1.判断n是否能被2~n-1间的数整除
最直观的方法，根据定义，因为质数除了1和本身之外没有其他约数，所以判断n是否为质数，直接判断从2到n-1是否存在n的约数即可。利用循环从2开始到n-1结束依次被该自然数整除，如果余数为0，则说明在2~n-1之间有该自然数的约数，那么，这个数不是素数。
2.判断n是否能被2~√n间的数整除
第一种判断方法，明显存在效率低的问题。对于自然数n，其实并不需要从2判断到n-1，我们知道，一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)（n的平方根），一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。
可以将判断一个数是否是素数的程序封装为一个函数：
再来分析题目，输入数据第一行二个自然数N,K，N表示有几本书，K为已有书的书号。
第二行输入N个整数，表示N本书的书号，显然，这里需要用数组来存放书号：
题目的输出要求是：最接近已有书号K的两个书号（一大一小），将找到的这两本书的书号加起来，并计算加起来以后的数是否为素数。
可以将存放在数组中的数据进行排序，同学们可能会想到很多排序的方法，冒泡排序，选择排序，插入排序等等。其实，我们也可以调用一个排序函数，这会使我们的程序更加简洁。
sort()函数用于C++中，对给定区间所有元素进行排序。头文件是#include <algorithm>
对于排序后的数组，只要满足条件：
a[i] < k && a[i + 1] > k也就找到了两个最接近目标书号的两个数据啦，接下来只需将两个数据求和并判断是否为素数即可。
怎么样？同学们是不是都已经有了编程思路了呢？小编这里也特别贴心的为大家写出完整的程序。如果还有疑问，可以留言咨询哦。
我们的冬令营C++入门班正在招生哦！想让你的假期更有意义更充实吗？想更多了解C++这门语言吗？快来报名参加吧！还有更多冬令营课程等你来体验哦。
每周六，周日上午10：00都有冬令营相关课程的免费试听课！快来预约报名吧！
helloworld少儿编程
电话：17361882359
地址：南京市玄武区仙鹤新天地广场2栋-302
欢迎来电咨询，还可以预约试听噢！