1007 素数对猜想 (20 分)Python参考答案
输入格式:
输入在一行给出正整数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 jishu20分的
#!/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
