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

看板Prob_Solve作者EdisonX (閉上眼的魚)時間12年前 (2011/11/29 10:17)推噓4(4推 0噓 2→)

留言6則, 3人參與討論串1/2 (看更多)

這問題是逛網路時看到的。 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

11/29 10:24, , 1^F

11/29 10:24, 1^F

→

musie

11/29 10:25, , 2^F

11/29 10:25, 2^F

推

musie

11/29 10:30, , 3^F

11/29 10:30, 3^F

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

→

LPH66

11/29 15:23, , 4^F

11/29 15:23, 4^F

第一次聽到漢米爾頓圈，謝謝提供 keyword.

推

musie

11/29 17:02, , 5^F

11/29 17:02, 5^F

聽起來像是不好搞的感覺，想說我寫的 code 跑非常久，是不是單純是我的問題 Orz. 謝謝 musie 大不吝賜教。 ※ 編輯: EdisonX 來自: 180.177.78.41 (11/29 19:54)

推

bigpigbigpig