將數字表示爲素數總和

我給出了一個大數n，我需要查找它是否可以表示爲K素數的總和。將數字表示爲素數總和

實施例9可以表示爲3素數的和作爲2 + 2 + 5。

我想使用子集總和的變化，但數量太大，直到那時生成所有的素數。

問題是從目前的HackerRank contest。限制是1 <= n, K <= 10^12

來源

2014-05-21 user3634974

對於K = 1，答案是明顯的「是」 IIF N是素數

對於K = 2，根據Goldbach conjecture，這是驗證對於N高達大約10^18，答案是「是「iif N是偶數並且N> = 4或者如果N - 2是素數。

有趣的情況是K = 3。顯然如果N < 6，答案是「否」，因爲可表示爲三個素數之和的最小數字是2 + 2 + 2 = 6。如果N≥6 ，那麼N - 2或N - 3是偶數和> = 4，所以我們可以再次應用哥德巴赫猜想。

因此，對於K = 3，答案是「是」簡單IIF N> = 6

通過感應（提示：只要使用的K - 3倍素2），我們可以表明，對於K> = 3，答案是「是」iif N> = 2 * K，所以只有K = 1和K = 2的情況是非平凡的，只需要一個簡單的素性檢查，例如通過O（log^4 N）中的Miller–Rabin。

編輯：作爲獎勵，這個證明也給出了一個建設性的算法來輸出分區。我們用2的數量，也許是3的數量來得到K = 2。棘手的K = 2，N的情況並不像看起來那麼困難：我們知道從Goldbach猜想的computational verification可知，對於N≥12，是一個Goldbach分區，素數爲< 5200左右。有不到700個這樣的素數，所以我們可以在合理的時間內檢查它們。

來源

2014-05-22 14:32:49

好，但這不會給你K素數p_1 + ... + p_K = n。大拇指爲米勒拉賓！ – Brainless

@Brainless那麼任務只是詢問是否存在分區。如果你想重建這個分區，這一切都會減少到哥德巴赫的猜想。根據計算驗證，我們知道有一個小素數的分區（根據http://sweet.ua.pt/tos/goldbach.html上的圖表，我認爲N <= 10^12時小於5000）），所以你可以負擔得起檢查它們（大約有700個候選素數），並測試N - p的素數。仍然非常可行。當然，除非K很大，這裏可能是這種情況，那麼輸出尺寸就會成爲問題。 –

從較大的K減少到K = 3只是使用（K-3）乘以素數2.然後使用2或3並且你在K = 2並且可能需要找到一個Goldberg分區，I在其他評論中描述 –

您正在尋找的概念被稱爲主分區的一個數字。計算一個數的主分區數的公式是\ kappa（n）= \ frac {1} {n} \ left（\ mathrm {sopf}（n）+ \ sum_ {j = 1}^{n- 1} \ mathrm {sopf}（j）\ cdot \ kappa（nj）\ right）;我在LaTeX中使用了這個符號，因爲我不知道如何在html中執行它。 sopf(n)函數是,,sopf(42) = 12，因爲42 = 2 * 3 * 7，但是sopf(12) = 5，因爲12 = 2 * 2 * 3，但是每個素因子被計數一次。我在my blog討論此公式。

來源

2014-05-21 18:29:37 user448810

我的問題是關於是否存在形成給定數字的K個素數。不是主分區的數量。 – user3634974

這很聰明，但計算速度太慢。這需要O（2^n）來計算，並且n非常大... – Brainless

你的輸入是n和K.有很多情況：

K> N：不可能
K = N：K個素數都爲1
ķ< N：4子情況：

a。 n和K是奇數

b。 n是偶數，K是奇數

c。 n是奇數，K是偶數

d。 n和K是偶數

案例a：選擇任何素數p < n和p> 2.問題歸結爲與輸入np和K-1相同的問題，而不是n和K，我們陷入情況b

情況b：問題分別減少到相同的問題與輸入的n-2和K-1，而不是n和K，和我們的情況下，d落入

情況c：同上比b，但我們跌倒情況d：如果n = 2K，則2，2，...，2取K次是你的解決方案（即你的素數是2，2，...，2）。否則n可寫成

n = (\sum_{i=1}^{i=K-2} 2) + p + q

其中我們在總和中加上素數2（K-2）次。然後，問題簡化爲與輸入n-2（K-2）相同的問題，而不是n和2，而不是K.但這是哥德巴赫。你可以像這樣在O（n sqrt（n））中求解它：把p和q都等於n/2。增加p並在每個步驟中將q減1，直到它們都是素數。

來源

2014-05-22 09:15:41 Brainless

如果2：1不是質數 – juver

這似乎是合法的，但它仍然太慢，但我認爲它可以改進運行時 - 明智的 –

將數字表示爲素數總和

回答

相關問題