About new_ Online_ Judge_ 1081_ Thoughts on Goldbach's conjecture

 Topic description :
 Enter a value not less than 6 The positive integer n, Split it into the sum of three primes , Output any solution .
 Input format 
 Multiple sets of test data exist in the input , Each row of test data input contains a positive integer n(6<=n<=20000)
 Output format 

#  See this topic , The first thought is to write a function to judge prime numbers 
def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    else: #  When for The cycle has not been break When interrupting , The return is a prime 
        return True

#  Then enumerate the possible results through the triple loop nested violence 
#  It looks something like this 

def solution1(n):
    for i in range(2,n):
        for j in range(2,n):
            for k in range(2,n):
                if i + j + k == n and all([isPrime(x) for x in (i,j,k)]):
                    return(i,j,k)

if __name__ == '__main__':
    print(solution1(20000)) #  programme 1 Overtime 

#  Heller , Next, we will start the slow long march of solving this problem 

""" analysis :
     programme 1, There are two time-consuming places :
         The first is isPrime() function , Complexity is O(n**05)
         The second is triple for Nesting of loops , Complexity is O(n**3)
"""

#  from isPrime() Start to improve , This is a step of all evil , Take me into the abyss . But if you can stand the gaze of the abyss , The abyss must give back .*
#  Search the data and find that there are two better algorithms for finding prime numbers , They are respectively called Ehrlich sieve and Euler sieve .

# 1  Ethmoid 
"""
 principle :
     Please see :https://blog.csdn.net/holly_Z_P_F/article/details/85063174?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165215199716780357271614%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=165215199716780357271614&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-85063174-null-null.142^v9^pc_search_result_cache,157^v4^control&utm_term=%E5%9F%83%E6%B0%8F%E7%AD%9B&spm=1018.2226.3001.4187
"""
#  Implementation code :

def eratosthenes(n):
    lis = list(range(n))
    for i in range(2,int(n**0.5)+1):
        k = i*i
        while k <= n-1:
            lis[k] = 0
            k += i
    return lis

#  The time complexity of the sieve is O(n*log(log n))

# 2 It can be further improved on the basis of Ehrlich sieve , That is, Euler sieve , That is, linear sieve , Because its time complexity is linear O(n)
#  For the principle of Euler sieve, please refer to :https://blog.csdn.net/qq_39763472/article/details/82428602?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165215228416781683989481%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=165215228416781683989481&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-82428602-null-null.142^v9^pc_search_result_cache,157^v4^control&utm_term=%E6%AC%A7%E6%8B%89%E7%AD%9B&spm=1018.2226.3001.4187
#  The code is as follows :

def ola(n):
    ''' Euler sieve for prime numbers '''
    lis = [True]*n
    lis[0] = lis[1] = False
    prime = []
    for i in range(2,n):
        if lis[i]:
            prime.append(i)
        for p in prime:
            if p*i >= n:
                break
            lis[i*p] = False
            if i % p == 0:
                break
    return prime

#  Write a decorator and simply count the time , Visually look at violence enumeration , Ethmoid , Comparison of running time of Euler sieve 
#  The code is as follows :
import time

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    else: #  When for The cycle has not been break When interrupting , The return is a prime 
        return True

def zhuangshiqi(func):
    def b(x):
        start = time.time()
        for i in range(100):
            func(x)
        end = time.time()
        print(" Program execution 100 The average time is :{:.4f}".format((end-start)*1000//100)," millisecond ")
    return b

@zhuangshiqi
def baoli(n):
    lis = []
    for i in range(2,n+1):
        if isPrime(i):
            lis.append(i)

@zhuangshiqi
def eratosthenes(n):
    lis = list(range(n))
    for i in range(2,int(n**0.5)+1):
        k = i*i
        while k <= n-1:
            lis[k] = 0
            k += i
    return lis

@zhuangshiqi
def ola(n):
    ''' Euler sieve for prime numbers '''
    lis = [True]*n
    lis[0] = lis[1] = False
    prime = []
    for i in range(2,n):
        if lis[i]:
            prime.append(i)
        for p in prime:
            if p*i >= n:
                break
            lis[i*p] = False
            if i % p == 0:
                break
    return prime

if __name__ == '__main__':

    print(" Start the violence enumeration ")
    baoli(10**6)
    print(" Start performing the sieve ")
    eratosthenes(10**6)
    print(" Start to implement Euler sieve ")
    ola(10**6)

""" give the result as follows :
 Start the violence enumeration 
 Program execution 100 The average time is :3189.0000  millisecond 
 Start performing the sieve 
 Program execution 100 The average time is :589.0000  millisecond 
 Start to implement Euler sieve 
 Program execution 100 The average time is :201.0000  millisecond 
"""

#  Good! , Great improvement in time , Although Euler sieve is not directly used to judge whether a number is a prime number , But to find less than n All prime numbers of 
#  But it's worth a try , So there is a second solution 

def solution2(n):
    #  Use the Euler sieve to find out all less than n The prime 
    lis = ola(n)
    for i in lis:
        for j in lis:
            for k in lis:
                if i + j + k == n:
                    return(i,j,k)

#  Very regret , Still timeout 

#  Then we have to find the sum of three numbers n Here we go .
#  Keep checking the data , Then I found a clever way to find the sum of three numbers with two pointers 
#  For a detailed analysis of the double pointer algorithm, please refer to 
# https://blog.csdn.net/weixin_42521211/article/details/88189536
#  The code is as follows :

def three_sum(lis,n):
    ''' Double pointer to find the sum of three numbers in the array is equal to n tuples '''
    leng = len(lis)
    for i in range(leng):
        l = i
        r = leng - 1
        while l <= r:
            if lis[i] + lis[l] + lis[r] == n:
                return (lis[i], lis[l], lis[r])
            elif lis[i] + lis[l] + lis[r] < n:
                l += 1
            else:
                r -= 1
#  So there is the following solution 
def solution3(n):
    #  Use the Euler sieve to find out all less than n The prime 
    lis = ola(n)
    res = three_sum(lis,n)
    for i in res:
        print(i,end=' ')

#  You must have guessed , This scheme is still timeout !!!!

---

  After this , Tried other methods , For example, the function of summation of three numbers is directly nested in Euler sieve , But this is a big hole , Time performance is very poor , Maybe there is something wrong with my code , Record the following :

#  This version attempts to insert the double pointer directly into the Euler sieve    Find more time ????


def three_sum(lis,n):
    ''' Double pointer to find the sum of three numbers in the array is equal to n tuples '''
    leng = len(lis)
    for i in range(leng):
        l = i
        r = leng - 1
        while l <= r:
            if lis[i] + lis[l] + lis[r] == n:
                return (lis[i], lis[l], lis[r])
            elif lis[i] + lis[l] + lis[r] < n:
                l += 1
            else:
                r -= 1

def ola(n):
    ''' Euler sieve for prime numbers '''
    lis = [True]*n
    lis[0] = lis[1] = False
    prime = []
    for i in range(2,n):
        if lis[i]:
            prime.append(i)
        if three_sum(prime,n):
            return three_sum(prime,n)
        for p in prime:
            if p*i >= n:
                break
            lis[i*p] = False
            if i % p == 0:
                break
    # return prime

def main():
    while 1:
        n = int(input())
        if n < 6:
            break
        res = ola(n)
        for i in res:
            print(i,end=" ")

if __name__ == '__main__':
    main()

  then , Consider not using lists , Use dictionary instead , Improve discovery performance ?

I'm sorry , All these plans failed .

---

#  Last, last , See the following scheme , Problem solved 

'''' When doing this, you need to have a certain understanding of Goldbach's conjecture , So as to deform the topic ,
 Otherwise, you will have to timeout .

 The common conjecture statement today is Euler's version , That is, any greater than 2 Even numbers of can be written as the sum of two prime numbers , Also known as “ Johann Goldbach conjecture ” or “ Goldbach's conjecture on even numbers ”.
 From Goldbach's conjecture about even numbers , Can be launched ： Any one is greater than 7 The odd numbers of can be expressed as the sum of three odd prime numbers . The latter is called “ Weak Goldbach conjecture ” or “ Goldbach's conjecture on odd numbers ”.

 First, process the even input data ：
 Subtract two from the input data , The remaining value is still an even number , Then we can find out the remaining two primes through violence ;

 When the input data is odd ：
 Subtract... From the input data 3, The remaining values are even , It is still through violence to find out the remaining two primes ;
————————————————
 Copyright notice ： This paper is about CSDN Blogger 「 get ！！」 The original article of , follow CC 4.0 BY-SA Copyright agreement , For reprint, please attach the original source link and this statement .
 Link to the original text ：https://blog.csdn.net/m0_46557490/article/details/119220492'''

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    else:
        return True


def main():
    while 1:
        n = int(input())
        if n < 6:
            break
        if n % 2 == 0:#  Even numbers 
            for i in range(2,n-2):
                if isPrime(i) and isPrime(n-2-i):
                    print(2,i,n-2-i)
                    break
        else:
            for i in range(2,n-3):
                if isPrime(i) and isPrime(n-3-i):
                    lis = [i,3,n-3-i]
                    lis.sort()
                    for i in lis:
                        print(i,end=' ')
                    break


if __name__ == '__main__':
    main()

#  The result is violent enumeration   Perfect victory   Euler screen  +  Double pointer   Ha ha ha ha ha ha ha ha 

Use the above code to pass , And then copied CSDN Blogger 「 get ！！」 Of c++ Compare the code

 c++ Or the king of performance

But C++ It's hard to learn !!!