Euler Project 挨个做 - 之一(Q1-50)

tree_new_bee

这个题，看似麻烦， 做起来很轻松：

with t as (select column_value p from table(pkg_prim2.seive_numlist(9999)) where column_value>1000)
select t1.p, t2.p, t3.p, t1.p||t2.p||t3.p  from t t1, t t2, t t3
where t1.p < t2.p  and t2.p<t3.p
and  translate('0123456789', t1.p||'0123456789', t1.p)= translate('0123456789', t2.p||'0123456789', t2.p)
and  translate('0123456789', t1.p||'0123456789', t1.p)= translate('0123456789', t3.p||'0123456789', t3.p)
and t3.p-t2.p = t2.p - t1.p
and t1.p <> 1487



         P          P          P T1.P||T2.P||T3.P
---------- ---------- ---------- --------------------------------------------------------------------------------
      2969       6299       9629 296962999629

Executed in 0.125 seconds

注意，其中的translate条件并不严密， 在4位数字中有重复数字时，会有漏网之鱼， 比如：会把1009与1019当作是互为排列。
我本来是打算加上其它条件等结果出来后，再修改条件的。
不过，加上其它条件后，只有上面的一条结果， 自然就无须再费神了。

这里，对translate的用法， 与http://www.itpub.net/thread-1382582-1-2.html 帖子中的用法相似。

tree_new_bee

Q50 Which prime, below one-million, can be written as the sum of the most consecutive primes?

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

tree_new_bee

这个题， 初看非常难。
要把每个数去分解成一系列质数的加法， 分解的方法太多了， 简直是个天文数字。看上去就似乎不可行。

所以，可以反过来：
从第一个质数开始，往后面累加。 累加到1000000以内的最大值。  如果这个累加数不是质数， 则考虑从最小的质数开始从中减去， 直到能得到一个质数为止。


用这样的方法， 人肉+程序辅助， 其实很快就能找到答案：

列出从2开始的质数， 及累加和：
with t as (select   column_value p from table(pkg_prim2.seive_numlist(4871)) )
,ts as (select   row_number() over (order by p) r, p, sum(p) over (order by p) s from t)
select * from ts

         R          P          S
---------- ---------- ----------
         1          2          2
         2          3          5
         3          5         10
         4          7         17
.....
       544       3923     989801
       545       3929     993730
       546       3931     997661
       547       3943    1001604

1001604要想减到100万以内，需要减很多小质数， 所以先不考虑。
997661如果是质数就好了， 那么它一定是那个最长的数！
可惜它不是， 从997661里分别减2,(2+3), (2+3+5)后， 发现997661-10=997651是个质数。  只减掉3个小质数就出现了， 而再小一点的几个数没有这么幸运。993730需要减掉(2-13), 989801需要减掉(2-17).
因此997651这个数的可能性非常大!

tree_new_bee

把上面的思路， 用SQL完整的描述出来：

with t as (select   column_value p from table(pkg_prim2.seive_numlist(5000)) )
,ts as (select   row_number() over (order by p) r, p, sum(p) over (order by p) s from t)
--select * from ts
,t1 as (select t1.r r1, t2.r r2, t1.p p1, t2.p p2, t1.s s1, t2.s s2, t1.r-t2.r rcnt, t1.s-t2.s thenumber from ts t1, (select * from ts union all select 0,0,0 from dual) t2
where t1.r - t2.r > 21 and t1.s-t2.s<=1000000
and pkg_prim2.isprim(t1.s-t2.s)=0)
select * from t1 where rcnt = (select max(rcnt) from t1)

        R1         R2         P1         P2         S1         S2       RCNT  THENUMBER
---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
       546          3       3931          5     997661         10        543     997651

Executed in 6.219 seconds

tree_new_bee

相应newkid的号召， 另开新楼：

http://www.itpub.net/thread-1383369-1-1.html

〇〇

ZT50
题目简介:素数41能写成连续6个素数之和：
　　　　41 = 2 + 3 + 5 + 7 + 11 + 13
　　现在要求1,000,000以内的素数，能表示为最多的连续素数之和的那个数。
题目分析:我这儿采取的是类似“迭代加深搜索”的算法：首先对“连续素数”的个数做一个上界估计，记为
len。然后看1000000以内有没有len个连续素数其和也为素数，并且在1000000以内。如果有，这这个和就是
解；否则，将len减1，继续上述操作。
答　　案:997651

〇〇

这个“连续”简化了问题

〇〇

50的sql版
var n number;
exec :n:=25000000
with ta as
(select level*2+1 l from dual connect by level<=sqrt(:N)/2),
t1 as (select level*2+1 l from dual connect by level<=sqrt(:N)/3)
,p1k as(select l rn from ta --1000以内的质数
minus
select /*+ USE_MERGE (t1 t2) */ t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(sqrt(:N))
and t1.l<=t2.l and t1.l*t2.l<=:N
)
,test as
(select rn, sum(rn) over(order by rn)s from p1k)
,t2 as(select max(s)s1,max(rn)rn1 from test where s<1E6)
select max(s1-test.s)from test,t2
where not exists(select 1 from p1k where p1k.rn <=sqrt(s1)and mod(s1-test.s,p1k.rn)=0);

MAX(S1-TEST.S)
--------------
        997651

已用时间:  00: 00: 00.19

yizhong010

数据库什么版本的？
我10G这提示不支持列别名

tree_new_bee

原帖由 yizhong010 于 2010-12-30 16:18 发表
数据库什么版本的？
我10G这提示不支持列别名

帖中所有的递归with语句 (即with 后面的表名后面带有括号的)， 都需要11.2以上版本。