超级素数-第12届蓝桥杯选拔赛Python真题精选

[导读]：超平老师的Scratch蓝桥杯真题解读系列在推出之后，受到了广大老师和家长的好评，非常感谢各位的认可和厚爱。作为回馈，超平老师计划推出《Python蓝桥杯真题解析100讲》，这是解读系列的第40讲。

超级素数，本题是2020年8月23日举办的第12届蓝桥杯青少组Python编程选拔赛真题。题目要求编程计算所有小于等于n的超级素数的个数，超级素数是指一个素数，依次去掉最后面的一个数字，总能保证剩下的数字依然是素数。

先来看看题目的要求吧。

一.题目说明

提示信息：

在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数，被称为素数，又叫质数。

超级素数是指一个素数，每去掉最后面的一个数字，总能保证剩下的数依然为素数。

比如：“373”就是一个超级素数，去掉个位的“3”后，“37”依然是素数；继续去掉“37”个位的 “7”后，“3”还是素数。

编程实现：

输入一个正整数 n (10 ≤ n ≤ 108)，输出所有小于等于n的超级素数的个数。

输入描述：

输入一个正整数 n (10 ≤ n ≤ 108)

输出描述：

输出所有小于等于n的超级素数的个数

样例输入1：

30

样例输出1：

6

样例输入2：

50

样例输出2：

8

样例输入3：

100

样例输出3：

13

样例输入4：

500

样例输出4：

21

样例输入5：

1000

样例输出5：

27

样例输入6：

3200

样例输出6：

34

二.思路分析

这是一道简单的数论问题，考查的知识点包括素数的判断、函数的定义和使用、枚举算法和拆位算法等。

根据题目的描述，对于输入的整数n，我们需要使用枚举算法从2到n逐个判断每个整数是否为超级素数。

本着偷懒的思想， 我们会这么想：如果有一个函数可以判断超级素数那就太方便了。

很显然，Python并没有提供这个函数。不过没关系，我们可以自定义一个函数，对于给定的整数，判断是否为超级素数，自己动手，丰衣足食嘛。

在判断超级素数过程中，需要依次去掉最低位，通常有两种方法：

• 字符串方法

• 数学方法

字符串方法是指将数字转成字符串，然后使用切片去掉最后一位，再转成数字。

数学方法则是使用拆位算法，对于任何一个整数，如果要获取最低位，只需要对10取余数即可， 然后再使用整除，去掉最低位。

举个例子，给定整数n = 168，第一次拆位过程如下：

第1步：取出个位，168 % 10 = 8第2步：去掉个位，168 // 10 = 16

经过第一次拆位，数字n变成了16，第二次拆位过程如下：​​​​​​​

第1步：取出个位，16 % 10 = 6第2步：去掉个位，16 // 10 = 1

经过第二次拆位，数字n变成了1，第三次拆位过程如下：​​​​​​​

第1步：取出个位，1 % 10 = 1第2步：去掉各位，1 // 10 = 0

此时，数字n变成了0，拆位结束。从这个过程中可以发现，如果需要最低位，就是n %10，如果需要去掉最低位的数字，就是n // 10。

当然，对于每一次取出的整数，又需要分配判断是否为素数。再次使用函数的编程思想，自定义一个函数用于判断是否为素数即可。

所以，我们可以将本题拆分如下3个过程：

• 定义函数判断素数

• 定义函数判断超级素数

• 枚举统计超级素数个数

思路有了，接下来，我们就进入具体的编程实现环节。

三.编程实现

根据上面的思路分析，我们分3步来编写程序：

• 定义函数判断素数

• 定义函数判断超级素数

• 枚举统计超级素数个数

1. 定义函数判断素数

根据前面的思路分析，我们定义函数is_prime()如下：

代码比较简单，简单说明4点：

1). 如果n<= 1，肯定不是素数，直接返回False；

2). 在计算n的平方根时，我们使用**0.5，**是Python独有的运算符，使用起来非常方便，当然，你也可以使用math模块中的sqrt()函数来计算；

3). 正常情况下，对于整数n，我们需要逐个判断2~n-1中的每一个数字，但实际上根据乘法的对称性（两个乘数是成对出现的，并且以平方根为轴对称的），只需要判断到n**0.5就可以，这可以大大提升算法的效率，不过需要注意range()函数虎头蛇尾（包含头不包含尾）的特点，需要加1才行；

4). 在2 ~ n ** 0.5之间，如果有能被整除的，则说明不是素数，返回False；如果循环结束，都没有返回False，则说明n是素数，直接返回True。

2. 定义函数判断超级素数

根据前面的思路分析，我们接着定义is_super_prime()函数如下：

代码不多，前面都已经详细分析过，这里就不再赘述了。只强调一点，在Python编程中，除法有两个运算符，分别是/和//，前者的结果是浮点数，后者才是整除。

3. 枚举统计超级素数个数

有了is_super_prime()函数，接下来就比较简单了，直接使用循环逐个判断即可，对应的代码如下：

注意，题目要求输出所有小于等于n的超级素数的个数，所以在range()函数中，第二个参数需要使用n + 1。

至此，整个程序就全部完成了，你也可以输入不同的数字来测试效果。

四.总结与思考

本题代码在18行左右，涉及到的知识点包括：

• 循环语句，包括while循环和for循环；

• 条件语句的使用；

• 自定义函数；

• 运算符的妙用；

• 枚举算法；

• 拆位算法；

判断素数是一个简单的数论问题，但也是一个非常重要的算法基础题，出现的频率也非常高。

大部分情况下，我们直接使用枚举算法逐个判断即可，但是当数字比较大的时候，算法的效率就显得有些低了，此时需要想想如何进行聪明的枚举，减少判断次数，从而提升效率。

最简单的改进方法就是利用乘数的对称性，去掉重复的判断，当然，还有一些更巧妙的办法，超平老师会在后续的教程中分享。

在解决本题的过程中，我们使用了函数的编程思想，相信你也感受到了，使用函数之后，代码的结构和逻辑变得更清晰了，这就是结构化思维的魅力。

超平老师反复强调，我们一定要强化自己的结构化思维，将一个复杂的问题拆分成若干简单的问题，然后逐个解决简单问题。一旦你真正具备了这种思维，你就会发现自己原来也可以这么厉害。

超平老师给你留一道思考题，除了本教程给出的方法，你还有什么更好的算法来判断素数吗。

你还有什么好的想法和创意吗，也非常欢迎和超平老师分享探讨。

如果你觉得文章对你有帮助，别忘了点赞和转发，予人玫瑰，手有余香