I wrote an answer in Zhihu a long time ago , I filled the hole today , By the way .
Let's define dn by ：dn=pn+1−pn, among pi It's No i Prime number . Obviously there is d1=1, And for n>1 Yes dn It's even .
“ Prime to guess ” Think “ There are infinite pairs of neighbors and the difference is 2 The prime ”. Now let's give any positive integer N(<10^5), Please calculate no more than N The number of prime pairs that satisfy the conjecture .
And the title also limits 400ms Time （ Is there a mistake (╯‵□′)╯︵┻━┻）
The first program I wrote ran longer than... At the maximum 10 second (;′⌒`)
Later I saw a person's answer on the Internet , Use the math knowledge learned in junior high school :
Suppose a number N Is the sum , It has a divisor a, So there are a×b=N
be a、b One of the two numbers must be greater than or equal to the root N, A sign less than or equal to the root N.
therefore , As long as it's less than or equal to the square root N Number of numbers （1 With the exception of ） Not divisible N, be N It must be prime .
Forgive me for not learning math well , According to this idea I wrote the following program ：
import math # Use math Module to square
import time # Calculate program run time
num = int(input()) # Enter an integer
s = 0 # Calculate the number of prime pairs
start = time.time() # Calculate start time
def f1(n):
if n <= 1:
return False
else:
for i in range(2, int(math.sqrt(n)) + 1): # here +1 Is to include the result of the square root
if n % i == 0:
return False
return True
for i in range(1, num+1):
if f1(i) is True and f1(i + 2) is True and (i + 2) <= num: # The final condition is to limit prime pairs to more than N
s += 1
end = time.time() # End time
print(s) # Print the number of prime pairs
print(end - start) # Output run time
Um. This is the general logic , The final time is greatly shortened , use 100000 To experiment , Time is 0.4561. Slightly more than 400ms.
What do I do …… So keep looking for , There are always people who have the same problems as me ？
Finally, I found ！
To continue to optimize and shorten the running time , It is to eliminate the redundant workload according to the above ideas . Now that we have eliminated half , Is it possible to rule out more ？
crap ！ Of course ~（ Otherwise, I would not write here ）
The first thing that comes to mind is even numbers ！ except 2 outside , Obviously even numbers are not prime numbers . well , Another half is excluded .
Follow the train of thought , Then the odd number can be 3, By 5 Even those divisible must be excluded .
Follow this line We get this code ：
import math # Use math Module to square
import time # Calculate program run time
num = int(input()) # Enter an integer
s = 0 # Calculate the number of prime pairs
start = time.time() # Calculate start time
def f1(n):
if n <= 1:
return False
elif n % 2 == 0 and n != 2: # Can be removed by 2 Divisible barring 2（ In fact, it can also include 2, think 2 There are no prime pairs ）
return False
elif n % 3 == 0 and n != 3: # Can be removed by 3 Divisible barring 3
return False
elif n % 5 == 0 and n != 5: # Can be removed by 5 Divisible barring 5
return False
elif n % 7 == 0 and n != 7: # Can be removed by 7 Divisible barring 7
return False
else:
for i in range(3, int(math.sqrt(n)) + 1, 2): # here +1 Is to include the result of the square root
if n % i == 0:
return False
return True
for i in range(1, num+1):
if f1(i) is True and f1(i + 2) is True and (i + 2) <= num: # The final condition is to limit prime pairs to more than N
s += 1
end = time.time()
print(s)
print(end - start)
use 100000 To experiment , The time you get is 207ms！！！ Qualified ！！！ Less than half ！ But can it be less ？
Really ！
To simplify , We have to understand the nature and distribution of twin prime numbers .
One . When n≥5 when , If one n-1,n+1 They are twin prime numbers , be n It must be 6 Multiple
obtain ：
Corollary one ： When x >= 1, (6x - 1) or (6x + 1) When it's not prime , namely
2(3x) - 1, 3(2x) - 1,
2(3x) + 1, 3(2x) + 1, When it is a composite number ,
Their prime factors do not include 2 and 3 Multiple .（ A composite number is a product that can be decomposed into multiple prime numbers ）
Two . For greater than 3 The prime number of , Only distributed in 6x-1 and 6x+1 In two series (x For the wrong 0 Natural number ). That is, they are all here 6 On both sides of a multiple of .
in other words , Greater than 5 The prime number of must be 6x Both sides , however 6x The two sides of are not necessarily prime numbers .
6x-1 The prime numbers in the sequence are negative prime numbers , The composite number is a negative composite number
6x+1 The prime numbers in the sequence are positive prime numbers , The composite number is a positive composite number
Okay , According to the previous and the above two properties .
You know , For greater than 3 The twin prime number of
The code is as follows ：
import math # Use math Module to square
num = 100000
s = 1 # The default consideration is （3,5）
def f1(n):
if n == 5 or n == 7:
return True
elif n % 5 == 0 and n % 7 == 0:
return False
else:
for i in range(3, int(math.sqrt(n)) + 1, 1): # here +1 Is to include the result of the square root .
if n % i == 0:
return False
return True
for i in range(5, num+1, 6):
if f1(i) and f1(i+2) and (i+2)<=num: # The final condition is to limit prime pairs to more than N
s += 1
# print((i,i+2),s)
print(s)
The final time is 85ms！！！, Less than half ！！！
This is to look for ideas from the perspective of judging whether it is a twin prime number pair , For whether it is a prime number , I think there is no need to repeat . Just write according to the above ideas .
In fact, I learned one thing from this little practice , Before doing something , Don't keep your head down at the beginning , Think first , analysis , To really grasp the essence of things , Get more satisfactory results .
