[閒聊] Project Euler-第51題

作者: jimfan (jimfan)   2017-09-16 23:03:19
剛剛靈光一閃,想到一個比較有效的演算法。用的語言是 APL。
劇烈進行中,感覺快找到那八個質數了.........
更新:
問題出處:https://projecteuler.net/problem=51
在下的 APL 程式碼:https://github.com/Jim-Fan/euler-apl/blob/master/051.apl
昨晚衝破了,要點其實不是被替換的數字而是沒被替換的。以例子中的 7個質數
為例:
56003 56113 56333 56443 56663 56773 56993
1. 先從 5位質數中找出第 3、4位相同的出來,姑且命名為集合 P
2. 從 P,將3、4位去掉,合拼餘下數字,轉化為十進整數,如此上列質數變為:
56003 -> 56..3 -> 563
56113 -> 56..3 -> 563
56333 -> 56..3 -> 563
(... 類同)
3. 如此 563將出現 7 次,由 563在 P的位置(index),可找到 56003、
56113... 等等
至於問題所需的 8個質數,問題係由於不知有多少個位,先假定為 6位(純粹
猜想)。並且不知道那些、多少數字需要被替換,唯有手動逐個組合試試。先
嘗試 2位替換(digit[1, 2], digit[1, 3]... digit[2, 3]... digit[2, 4]
... 等等。遍尋不獲再試 3位替換,終於試出答案係 digit[1, 3, 5] 被換的
質數。

Links booklink

Contact Us: admin [ a t ] ucptt.com