我想找到總和爲給定值的最小素數集合，例如， 9 = 7 + 2（不是3 + 3 + 3）。找到總和到給定值的最小素數
我已經生成使用sieve of eratosthens
我穿越降序排列得到陣列最大素數小於或等於給定數量的陣列素數的數組。如果數字很奇怪，這個效果很好。 但偶數失敗，例如122 = 113 + 7 + 2但122 = 109 + 13。
從Golbach's Conjecture我們知道任何偶數都可以表示爲兩個素數的和。所以如果一個數字是偶數，我們可以直接返回2作爲輸出。
但我試圖找出一種方式比蠻力找到最小素數。
雖然你的問題沒有這麼說，但我假設你正在尋找一組具有最小基數的素數。
如果Ñ是偶數，則考慮素數p爲了，2，3，5，＆hellip ;;最終n - p將是素數，所以n是兩個素數的總和。這個過程通常會很快收斂，兩個素數中的較小者幾乎不會超過1000（通常比那個小得多）。
如果Ñ爲奇數，並且Ñ - 圖2是素數，則Ñ是素數的總和2和Ñ - 2.
如果Ñ是奇數，並且n - 2不是素數，那麼n-3是偶數，可以寫成兩個素數的總和，如上所述。
因此你總是可以找到兩個或三個素數之和即對任何目標比3
是的，我明白了這一點，但我想通過遍歷數組而不是使用Golbach猜想來找到它。正如我已經在我的問題中已經說過的奇數遍歷數組降序，以發現總和完美，但不是偶數。至於122的情況，所以我很好奇任何其他方法towrads遍歷。我希望我現在已經說清楚了。 – leo
我想我不明白你的最低定義。例如，122 = 2 + 7 + 113 = 13 + 109。如果「最小」意味着基數最小的集合，那麼13 + 109只有兩個成員。如果「最小」意味着具有最小最小元素的集合，那麼2 + 7 + 113的元素爲2.我想你更喜歡13 + 109解決方案，這是我的算法找到的解決方案。差別似乎是我從最小的素數開始，從最大的素數開始。 – user448810
更大ñ「所以，如果一個數是偶數，我們可以直接返回2作爲輸出」 - AHM，不，它是一個猜想... –
@Meiko好吧，它尚未被證明是錯誤的。所以我們可以放心地認爲它是正確的。 :) – leo
@Meiko哥德巴赫的猜想已被證實可以保持4 x 10^16，因此取決於利奧在做什麼（例如只使用32位數字），返回2可能有意義。 –