1. Topic description
1007 Pairs of prime guesses (20 points)
Let’s define d**n as: d**n= P **n+1− P **n, where P ** I is the i-th prime. Obviously d1=1, and d**n is even for n>1. The “prime pair conjecture” holds that “there are infinitely many pairs of prime numbers that are adjacent and differ by 2”.
Given any positive integer N(<105), please count the number of prime pairs that satisfy the conjecture not exceeding N.
Input format:
The input gives a positive integer N on one line.
Output format:
Print no more than N pairs of prime numbers satisfying the conjecture in one line.
Example Input:
20
Copy the code
Example output:
4
Copy the code
2
Definition of prime: A natural number greater than 1 that has no factors other than 1 and itself.
To find prime pairs, first find all the primes <=N and put them in a list.
So it was natural to write an algorithm to determine whether a number is prime
According to the above flow, we can translate it into code.
def 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 True
Copy the code
But writing it this way is very slow.
In this case, the total time limit is 200ms.
Although the above code is completely correct, but the last test point, directly run timeout, naturally can not get full marks.
So we need to design a faster algorithm for determining prime numbers.
2,3,5,7,11,13,17,19,23
Copy the code
If you look at the numbers above, you can see that all prime numbers greater than 6 can be expressed as 6K-1 or 6K +1. (k > = 1)
So we have algorithm 2
def isprime(n) :
if n == 2 or n == 3:
return True
if n % 2= =0 or n % 3= =0:
return False
for 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 False
return True
Copy the code
3. The AC code
import math
def 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 True
if n == 2 or n == 3:
return True
if n % 2= =0 or n % 3= =0:
return False
for k in range(6.int(math.sqrt(n)) + 2.6) :if n % (k-1) = =0 or n % (k+1) = =0:
return False
return True
n = int(input())
l = [i for i in range(2, n+1) if isPrime(i)]
count = 0
for index, element in enumerate(l):
if index < len(l)-1:
if l[index+1]-l[index] == 2:
count += 1
print(count)
Copy the code
This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign