前言

写这个专题的原因是我在切题的过程中发现了许多与素数相关的题目，都需要以素数为基础解题，索性就归结为一个专题一起发出来了。

一、判断素数

题目

描述

素数又称质数：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除。

输入格式

一个大于等于2的整数

输出格式

是素数，输出“Yes”，否则输出“No”。

样例

输入数据 1

31

输出数据 1

Yes

提示

建议对枚举范围适当的优化

分析

主要就是枚举范围属于2到n开根号，否则很可能会Runtime Error。

代码

a = int(input())
ans = "Yes"
for i in range(2, int(a ** 0.5) + 1):
    if a % i == 0:
        ans = "No"
        break
print(ans)

二、输出N以内的素数个数

题目

描述

输出n以内的素数个数（包含n）。

输入格式

一个大于等于2的正整数n。

输出格式

一个整数，即素数个数。

样例

输入数据 1

10

输出数据 1

4

提示

无

分析

建议先判断非素数的数再用总数减去，主要是计算素数个数不如非素数个数方便。

代码

n = int(input())
ans = 0
for i in range(2, n + 1):
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            ans += 1
            break
        j += 1
    i += 1
print(n - ans - 1)

三、回文素数

题目

描述

如果一个正整数只能被1和它本身整除，这个数就是素数。如果一个数从左到右和从右到左看都是一样的，称这个数为回文数。既是素数又是回文数的为回文素数。

编写程序，输入正整数a和b（2≤a≤b），列举出[a,b]范围内的所有回文素数，若没有回文素数，则输出0。

输入格式

以空格分隔的两个整数a和b

输出格式

一行若干个回文素数，各回文素数之间以“,”号分隔。

样例

输入数据 1

6 20

输出数据 1

7,11

提示

无

分析

我先讲一下我自己做题时的第一思路（其实就是刚开始写时踩的坑），一开始的思路是先判断素数，然后再用一个变量倒着循环素数看看是否满足回文这一要求（没想到切片），这时候就面临了第一个问题，怎么确定是素数，凭借我贫瘠的知识，我只能联想到之前做过的判断素数（用flag来确定）。后来又面临了第二个问题，如何在每个输出后面都加个逗号，由于第一次遇到这种输出的题目，我在end上死磕半天，结果是失败的，告诫大家不要这样做，因为end会在每个输出后面都加上一个","，包括最后一个输出，很显然不满足题目的输出要求，怎么解决下面会说。

接下来回归正题，先解决判断是否为素数的问题，我们只需要现将flag赋值为True，如果循环发现了因子，就让flag变成False，然后判断，如果flag是False就跳出判断是否为素数的循环，并直接进入下一个数的判断（我感觉这里我写的代码有点屎山，但是想不出什么办法了，求优化）。当flag等于True时才会继续执行，我们只需将这个数转为str，用切片判断其是否为素数，这时，解决上面第二个问题的方法来了，用列表来存储这个数（这里我有一个问题，希望有大佬能帮忙解答一下，就是为什么一个2位数x类似'11'，如果我有一个列表lst，我写成lst += x得到的结果是['1', '1']而不是['11']），我们将所有判断出来的回文素数都存储在列表中，最后用循环并根据它在列表中的位置判断是否需要在后面加逗号。

素数判断的范围优化：仅需循环到n开根号。

代码

a, b = map(int, input().split())
l = []
ans = 0
for i in range(a, b + 1):
    flag = True
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            flag = False
            break
    if flag == False:
        continue
    x = str(i)
    if x == x[::-1]:
        ans += 1
        l.append(i)
if ans == 0:
    print(0)
else:
    for p in range(len(l)):
        if p < len(l) - 1:
            print(l[p], end = ",")
        else:
            print(l[p])

四、哥德巴赫猜想

题目

描述

任何一个大于等于4的偶数，都可以用两个素数之和表示，但有些偶数的素数之和表示不唯一，如10有两种表示：10=3+7,10=5+5。

编写判断素数的自定义函数，验证哥德巴赫猜想：任意输入一个偶数，输出该偶数的所有素数之和。

输入格式

一个大于等于4的偶数

输出格式

若干行，每行一个算式

每个算式的第一个运算数从小到大排列；算式的第一个运算数≤第二个运算数；算式以“=”和“+”相连，中间没有空格，如样例所示

样例

输入数据 1

10

输出数据 1

10=3+7
10=5+5

提示

无

分析

这道题的思路是先找出(n-2)以内的所有素数，然后将它们都存储在一个列表中，再循环这个列表，当a和(n-a)都在这个列表中时，就输出它。

用in来判断是否在列表中。

代码

n = int(input())
s = []
for i in range(2, n - 1):
    flag = True
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            flag = False
            break
    if flag == True:
        s.append(i)
for k in s:
    if (n - k) in s and k <= (n - k):
        print(str(n) + "=" + str(k) + "+" + str(n - k))