1. 題目描述

1007 素?cái)?shù)對(duì)猜想 (20 分)

讓我們定義d**n為：d**n=p**n+1?p**n，其中p**i是第i個(gè)素?cái)?shù)。顯然有d1=1，且對(duì)于n>1有d**n是偶數(shù)。“素?cái)?shù)對(duì)猜想”認(rèn)為“存在無(wú)窮多對(duì)相鄰且差為2的素?cái)?shù)”。

現(xiàn)給定任意正整數(shù)N(<105)，請(qǐng)計(jì)算不超過(guò)N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)。

輸入格式:

輸入在一行給出正整數(shù)N。

輸出格式:

在一行中輸出不超過(guò)N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)。

輸入樣例:

20

輸出樣例:

4

2. 題目分析

素?cái)?shù)定義：在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)的自然數(shù)。

要求素?cái)?shù)對(duì)，首先要求出<=N的全部素?cái)?shù)，并把它放到一個(gè)list中。

所以自然而然想到要寫出一個(gè)算法，判斷一個(gè)數(shù)是否是素?cái)?shù)

根據(jù)上面的流程，我們將其可以翻譯成代碼。

def isPrime(n):if n == 1:return Falseend = int(math.sqrt(n))for i in range(2, end+1):if n % i == 0:return Falsereturn True

但是這樣寫算法的運(yùn)行效率非常慢。

這一題，限制的總耗時(shí)是200ms。

雖然上面的代碼處理完全正確 , 但是最后一個(gè)測(cè)試點(diǎn)，直接運(yùn)行超時(shí)，自然拿不到滿分。

所以我們要設(shè)計(jì)運(yùn)算速度更快的判斷素?cái)?shù)算法。

2,3,5,7,11,13,17,19,23

觀察上面的數(shù)字，可以看出所有>6的素?cái)?shù)，都可以采用 6k-1 或者 6k+1 的形式表示。（k>=1)

所以就設(shè)計(jì)出了算法2

def isprime(n):if n == 2 or n == 3:return Trueif n % 2 == 0 or n % 3 == 0:return Falsefor k in range(6,int(math.sqrt(n)) + 2, 6):# range取值 [6,12,18,...]if n % (k-1) == 0 or n % (k+1) == 0:return Falsereturn True

3. AC代碼

import mathdef isPrime(n): # if n == 1: # return False # end = int(math.sqrt(n)) # for i in range(2, end+1): # if n % i == 0: # return False # return Trueif n == 2 or n == 3:return Trueif n % 2 == 0 or n % 3 == 0:return Falsefor k in range(6,int(math.sqrt(n)) + 2, 6):if n % (k-1) == 0 or n % (k+1) == 0:return Falsereturn Truen = int(input()) l = [i for i in range(2, n+1) if isPrime(i)]count = 0for index, element in enumerate(l):if index < len(l)-1:if l[index+1]-l[index] == 2:count += 1print(count) 與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的【Python】PAT-1007-素数对猜想的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。