作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 425 Prime connection
时间Sun Apr 28 11:38:09 2013
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
1F：推 utomaya:图论的问题；质数是顶点 「有关系」代表两点之间有边连接 04/28 15:29
2F：→ tml:似乎是近几个礼拜最简单的一题了...破百的时间居然是14小时 04/29 12:47