4188: 差值最小质数对

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：1

题目描述

    给定一个大于2的偶数，在所有满足“任意一个大于2的偶数可以由两个质数相加得到”这个特点的质数对中，找出两个质数差值最小的一对，并将差值输出（差值为大数减小数的值，两个质数相等时差值为0）。

    例如：偶数16，满足特点的质数对有（5，11）和（3，13），差值最小的一对是（5，11），11减5，差值为6。

输入

输入一个大于2的偶数n

输出

输出满足“任意一个大于2的偶数可以由两个质数相加得到”这个特点的所有质数对中，差值最小的那一对的差值

样例输入 复制 

16

样例输出 复制 

6

提示

编程思路：

1. 找出2到n之间所有质数，放到质数列表ls中；

2. 因为要找两个差值最小的一对质数，不难推断应该是离n中间最近的一对质数。所以，从n的一半开始往前找，如果这个数是质数而且n减去这个质数的差也在这个质数列表中，则其差值即为差值最小的那一对质数；

    如果使用以前学过的方法找2到n之间所有的质数，存在效率很低的问题，当n>=10000时，运行时间会超过10秒。我们需要找到一个更高效率的方法。 

n=int(input())
ls=[]
for i in range(2,n+1):
    flag=True
    for j in range(2,i):
        if i % j==0:
            flag=False
            break
    if flag:
        ls.append(i)
for i in range(n//2,n+1): #中间往前找第1个质数
    if i in ls and n-i in ls:
        print(i+i-n)
        break

来源/分类

提交提交记录统计露一手!