[問題] 1~20數列,相鄰/頭尾和為質數

[EdisonX (閉上眼的魚)]

這問題是逛網路時看到的。

1~20 排成一列，使得任二相鄰之和為質數，且第一個數與最後一個數之和也為質數。

要找出所有解。

我的想法也點暴力，因任何數最大和只到39，所以先建 39 以下的質數表，

又因相鄰之二數必為一奇一偶 (加起來才會是奇數)，所以分二個 array 做 permutation

這樣從 20P20 = 2.43E18 降到 (10P10)**2 = 1.32E13，

還是跑很久！

另外的想法是用 bool used[21]={fase};

再進行質數之拆解，像 19 可拆成 1/18 2/17 3/16....

不過想法到這裡就卡住了，不知各位版友對於這問題有何想法？

--
If there is no tomorrow,
   I want to see u last time.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.78.41
推 musie:我是會先想列出所有兩者一組的和會是質數的配對
→ musie:再從中挑出所有數不重複的組合，再串起來
推 musie:其實能夠挑出來就結束了..根本就不用串
   我在想我的想法有沒有問題。

   若挑37去拆的話,有20.17/19.18/18.19/17.20,變 4*9P9*9P9
   挑19去拆的話，就變 9*9P9*9P9, 挑哪個質數拆會影響嗎？
   另請教為何挑出來就結束了?指的是能找到一組解後便能由
   Rotation + Reverse 變成其他解,所以不需串嗎 ?
   謝謝賜教。

→ LPH66:說起來找出相加組合之後這問題就變成漢米爾頓圈問題了...
   第一次聽到漢米爾頓圈，謝謝提供 keyword.

推 musie:數值不大，NPcom就硬幹處理
   聽起來像是不好搞的感覺，想說我寫的 code 跑非常久，
   是不是單純是我的問題 Orz.  謝謝 musie 大不吝賜教。
※ 編輯: EdisonX         來自: 180.177.78.41        (11/29 19:54)
推 bigpigbigpig:其實只有56組數目需要嘗試，這樣sample space小很多