孙肖宁

1007 素数对猜想 (20 分)Python参考答案
输入格式:输入在一行给出正整数N。输出格式:在一行中输出不超过N的满足猜想的素数对的个数。输入样例:20输出样例:...
扫描右侧二维码阅读全文
30
2019/09

1007 素数对猜想 (20 分)Python参考答案

1.png
输入格式:
输入在一行给出正整数N。

输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:
20
输出样例:
4

分析

在分析之前,小编先说下python的运行效率是真的不是很高,小编的算法优化了好几次才可以,最后的一个测试用例总是超时,20分的算法题只能拿18分,有强迫症的小编好难受,终于功夫不负有心人,完美解决。
大体的思路就是先判断素数,然后判断两个相邻的素数是否相差为2.
细节:

  • 偶数肯定不是素数。
  • 最小的素数对是3,5
  • 求素数的时候先开方,具体理由自己思考。

代码

18分的代码(经历就不说了)

#!/usr/bin/python
import math
n = input()

t = 1
jishu = 0

for num in range(2, n+1):
    chushu = math.sqrt(num)
    f = True
    for number in range(2, int(chushu)+1):
        if num%number==0:
            f = False
            break
    if f:
        if(num-t==2):
            jishu+=1
        t = num
print jishu

20分的

#!/usr/bin/python
import math
n = input()
def issushu(num):
    chushu = math.sqrt(num)
    for number in range(3, int(chushu)+1, 2):
        if num%number==0:
            return False
    return True

t = True
jishu = 0
for number in range(3, n-1, 2):
    t2=issushu(number+2)
    if t and t2:
        jishu+=1
    t = t2
print jishu
Last modification:October 2nd, 2019 at 10:56 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment