Source: Prime Sum

Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number.

NOTE A solution will always exist. read Goldbach’s conjecture

Example:


Input : 4
Output: 2 + 2 = 4

If there are more than one solutions possible, return the lexicographically smaller solution.

If [a, b] is one solution with a <= b,
and [c,d] is another solution with c <= d, then

[a, b] < [c, d] 

If a < c OR a==c AND b < d.

解題：

  1. 忍不住想先吐槽最後的條件非常脫褲子放屁。兩個不同組合[a, b] & [c, d]，啊如果a == c的話b是要怎麼樣才會 != d 啊……
  2. 這是一個關於哥德巴赫猜想的問題：每個大於2的偶數均可以拆分成兩個質數相加（不包含2）。一開始我也以為首先要做的事情就是先找出小於目標數的所有質數，而找質數的方式通常是採用數字由小往上到目標值開根號+1看是否有任何一數可整除該數，如無則該數即為質數；
  3. 但在這題如果採用這個方法，最大的問題就在於我們並非要找此數的質因數，而是要找所有小於此數的質數，用這個方式則每次在遇到每個數字時都需要做一次質數驗證，在網站上交卷測試時必定會timeout；
  4. 另一個方式則是不找該數的質因數，而是把數字擴展為一個陣列，並在遇到每一個質數之後將所有小於目標值但可被該質數整除的所有值標記為非質數；於後續測試a跟b是否均為質數時僅需要檢視其標記即可，基本上也是用空間複雜度換取較快的處理速度。

code:


class Solution:
    # @param A : integer
    # @return a list of integers
    def primeUpdate(self, A):
        output = [True]*(A+1)
        output[0], output[1] = False, False
        for i in range(4, A+1, 2):
            output[i] = False
        for i in range(3, int(pow(A, 0.5))+1, 2):
            for j in range(i*2, A+1, i):
                output[j] = False
        return output

    def primesum(self, A):
        if A == 4: return [2,2]
        prime_statues = self.primeUpdate(A)
        for i in range(3, A, 2):
            if prime_statues[i] and prime_statues[A-i]:
                return [i, A-i]

GitHub: GitHub

發表留言