题解 | #查找组成一个偶数最接近的两个素数#

import sys
#定义一个判断素数的遍历方法，这里的n是不是平方根对这种思路的算法影响不大
def isPrime(n):
    for i in range(2,n):
        if n % i == 0:
            #碰到整除的说明不是素数
            return False
    return True
 
n = int(input())
#数组从0开始，好处是index是对应素数，1代表是素数，0则不是
prime_list = [1 for _ in range(n+1)]
#初始化多余数据 0 1
prime_list[0]=prime_list[1]=0
for i in range(2,n+1):
    #从2开始遍历，如果标记是素数，算了一下确认是素数，则其倍数位置都不是素数
    if prime_list[i] == 1 :
        if isPrime(i):
            for j in range(i**2,n+1,i):
                #此处起点二次方可以免除重复赋值，原理：素数试除法：除数大于1且小于等于n的平方根
                #步进i代表倍数，n+1是上限
                prime_list[j] = 0
#偶数n对半，向左向右遍历，如果两个都素，就可以输出，此时距离最近
n1=n2=n//2
while prime_list[n1]+prime_list[n2] != 2:
    n1 -= 1
    n2 += 1
print(n1)
print(n2)
 

本文题目：查找组成一个偶数最接近的两个素数_牛客题霸_牛客网

本文：思路启发来源：五分钟小知识：如何用算法高效寻找素数？_吴师兄学算法