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