推 utomaya:圖論的問題；質數是頂點 「有關係」代表兩點之間有邊連接 04/28 15:29
→ tml:似乎是近幾個禮拜最簡單的一題了...破百的時間居然是14小時 04/29 12:47
425. Prime connection
http://projecteuler.net/problem=425
我們稱兩正整數A,B「有關係」（記作A↔B）如果下列任一條件成立：
(1) A和B的位數相同，並且只差一個數字；例如123↔173。
(2) 在A（或B）的最左邊添加一數字可以得到B（或A）；例如23↔223以及123↔23。
給定一質數P，如果存在一條質數關係鏈從2連結到P，並且每個關係鏈中的質數都比P小，
則我們稱P為「2的親戚」。
例如，127即為2的親戚，其中一條關係鏈表示如下：
2↔3↔13↔113↔103↔107↔127
然而，11和103都不是2的親戚。
令F(N)為不大於N的質數中，不是2的親戚的數的總和。
可以證明F(10^3) = 431以及F(10^4) = 78728。
請求出F(10^7)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.2.129.163