质数对

Input: 正整数N (N < 10^5)Output:计算<=N的质数对个数
质数对：差值为2的质数一组

第一版，(搞错题目意思)

以为是将所有差为2的质数排列，取出最长的序列@@

def checkPrime(num):    i = 2    while i <= int(num/2):        if num % (i+1) == 0:            return False        i +=1    return TrueiInput = int(input())lst = []i = 2while i <= iInput:    if i ==2:        lst.append(i)    elif i % 2 != 0 :        if checkPrime(i):            lst.append(i)    i +=1lst_tmp = []lst_rtn = []for i in range(len(lst)):    if i == 0 or lst[i] == lst[i-1] +2 :        lst_tmp.append(lst[i])    else:                if len(lst_tmp) > len(lst_rtn):            lst_rtn = lst_tmp        #print(lst_tmp)        lst_tmp = [lst[i]]  print(lst)print(lst_rtn)print(len(lst_rtn))

执行

20 #Input[2]       #list 1[3, 5, 7] #list 2[11, 13]  #list 3[2, 3, 5, 7, 11, 13, 17, 19] #20内的所有质数[3, 5, 7] #取出最长list3         #最长的list个数

第二版，(终于搞懂题目意思，但过不了最大测资)

只要差为2的质数即为一对，计算输入的数字内有几对质数对
举例：Input 20，[3 5],[5 7],[11 13],[17 19]，有4对质数对

def checkPrime(num):    i = 2    while i <= int(num/2):        if num % (i+1) == 0:            return False        i +=1    return TrueiInput = int(input())lst = []i = 2icount = 0iIndex = -1while i <= iInput:    if i ==2:        lst.append(i)        iIndex +=1    elif i % 2 != 0 :        if checkPrime(i):            lst.append(i)            iIndex +=1            if iIndex > 0 and lst[iIndex] == lst[iIndex-1] +2 :                icount+=1    i +=1print(icount)#Input:20#Answer:4

第三版，修正1(最大测资还是超时)

经高人指点...

判断质数只要计算到开根号(竟然忘了!)判断质数，+=2递增，可以略过偶数不用判断原本是用Empty list再判断塞资料，-->改成先将list塞进[2,3]，不用判断list[-1],list[-2]是否存在

def checkPrime(num):    #进来的数不会有偶数，从5开始+=2    i = 3    while i <= int(num ** 0.5):        if num % i == 0:            return False        i +=2 #进来的数不会有偶数，直接用+=2递增    return TrueiInput = int(input())lst = [2,3]i = 5icount = 0while i <= iInput:    if checkPrime(i):        lst.append(i)        #先在lst塞好2个值，也不需判断iIndex > 0        if lst[-1] == lst[-2] +2 :            icount+=1    i +=2 #+=2就不会有偶数可省略判断偶数print(icount)#最大测资Input:99999,Output:1224 673ms  超时

第四版，修正2(最大测资终于过了)

只有将判断质数，从while改写成for

import datetimedef checkPrime(num):    #进来的数不会有偶数，从5开始+=2    for i in range(3,int(num ** 0.5)+1, 2):        if num % i == 0:            return False    '''从while改写成for    while i <= int(num ** 0.5):        if num % i == 0:            return False        i +=2 #进来的数不会有偶数，直接用+=2递增    '''    return TrueiInput = int(input())starttime = datetime.datetime.now()lst = [2,3]i = 5icount = 0while i <= iInput:    if checkPrime(i):        lst.append(i)        #先在lst塞好2个值，也不需判断iIndex > 0        if lst[-1] == lst[-2] +2 :            icount+=1    i +=2 #+=2就不会有偶数可省略判断偶数print(icount)#After long runningendtime = datetime.datetime.now()print ('Run time:',(endtime - starttime).microseconds / 1000 ,'ms')#最大测资99999, 164ms

第五版，修正3(优化把所有while都改成for)

把所有while都改成for

import datetimedef checkPrime(num):    #进来的数不会有偶数，从5开始+=2    for i in range(3,int(num ** 0.5)+1, 2):        if num % i == 0:            return False    return TrueiInput = int(input())starttime = datetime.datetime.now()lst = [2,3]i = 5icount = 0for i in range(5,iInput+1,2):#while i <= iInput: --把while改写成for    if checkPrime(i):        lst.append(i)#        if lst[-1] == lst[-2] +2 :            icount+=1    #i +=2 #+=2就不会有偶数可省略判断偶数 --把while改写成forprint(icount)#After long runningendtime = datetime.datetime.now()print ('Run time:',(endtime - starttime).microseconds / 1000 ,'ms')#最大测资99999, 164ms

---

本文纯自己做题目之笔记，如有更好的方法再麻烦各位指教~~