4189: 埃氏筛法
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：2
题目描述
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。
埃式筛法的思路非常简单，就是用已经筛选出来的素数去过滤所有能够被它整除的数，即它的整数倍。这些素数就像是筛子一样去过滤自然数，最后被筛剩下的数自然就是不能被前面素数整除的数，根据素数的定义，这些剩下的数也是素数。
给出要筛数值的范围n，找出n以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。
给定一个大于2的偶数，在所有满足“任意一个大于2的偶数可以由两个质数相加得到”这个特点的质数对中，找出两个质数差值最小的一对，并将差值输出（差值为大数减小数的值，两个质数相等时差值为0）。
例如：偶数16，满足特点的质数对有（5，11）和（3，13），差值最小的一对是（5，11），11减5，差值为6。
样例输入 复制
16样例输出 复制
6提示
n=int(input())
a=[1]*(n+1)
ls=[]
for i in range(2,n+1):
if a[i]==1:
ls.append(i)
for j in range(i*2,n+1,i):
a[j]=0
for i in range(n//2,n+1):
if i in ls and n-i in ls:
print(i+i-n)
break
n=int(input())
a=[1]*(n+1)
ls=[2]
for i in range(3,n+1,2):
if a[i]==1:
ls.append(i)
for j in range(i**2,n+1,i*2):
a[j]=0
for i in range(n//2,n+1):
if i in ls and n-i in ls:
print(i+i-n)
break