Project Euler解题汇总(更新至309在1楼)

〇〇

--利用1/i的极限等于999...9/(i*10^n)的原理

--若 1/i=0.(b)则1/i=b(1/10^n+1/10^2n+。。)等比数列求和
set serverout on

declare
max1 number:=1;
l number:=0;
pos number:=1;
mod1 number:=1;
mod2 number:=1;
str1 varchar2(4000):='0.';
str2 varchar2(4000):='0.';
begin
for i in 980..999 loop
        str1:='0.'||lpad('0',length(i)-1,'0');
        mod1:=power(10,length(i));
        mod2:=power(10,length(i))-1;
for j in 1..999 loop
        mod1:=mod(mod1*power(10,length(i)),i);
str1:=str1||to_char(trunc(mod2/i));
mod2:=mod(mod2,i);
if mod1=0 then
--dbms_output.put_line('有限小数i=1/'||i);
goto exit1; /*有限小数*/
end if;
if mod2=0 then
pos:=case when (j*length(i))>max1 then i else pos end;
str2:=case when (j*length(i))>max1 then str1 else str2 end;
max1:=case when (j*length(i))>max1 then (j*length(i)) else max1 end;
--dbms_output.put_line('循环小数i=1/'||i||',长度='||(j*length(i))||',str=('||substr(str1,1,200)||')');
goto exit1; /*循环小数循环节*/
end if;
--mod2:=mod2*power(10,length(i))+power(10,length(i))-1;
l:=length(mod2);
mod2:=rpad(mod2,length(i),'9');
mod2:=case when mod2>i then mod2 else mod2||'9' end;
str1:=str1||rpad(0,length(mod2)-l-1,'0');
end loop;
<<exit1>>
NULL;
end loop;
dbms_output.put_line('最长i='||pos||',长度='||length(str2)||', 0.(');
for i in 1..length(str2)/47 loop
dbms_output.put_line(substr(str2,3+(i-1)*47,47));
end loop;
dbms_output.put_line(')');
end;
/

最长i=983,长度=984, 0.(
00101729399796541200406917599186164801627670396
74465920651068158697863682604272634791454730417
09053916581892166836215666327568667344862665310
27466937945066124109867751780264496439471007121
05798575788402848423194303153611393692777212614
44557477110885045778229908443540183112919633774
16073245167853509664292980671414038657171922685
65615462868769074262461851475076297049847405900
30518819938962360122075279755849440488301119023
39776195320447609359104781281790437436419125127
16174974567650050864699898270600203458799593082
40081383519837232960325534079348931841302136317
39572736520854526958290946083418107833163784333
67243133265513733468972533062054933875890132248
21973550356052899287894201424211597151576805696
84638860630722278738555442522889114954221770091
55645981688708036622583926754832146490335707019
32858596134282807731434384537131230925737538148
52492370295015259409969481180061037639877924720
24415055951169888097660223804679552390640895218
718209562563580874872838250254323499491353
)

[ 本帖最后由 〇〇 于 2010-11-8 09:15 编辑 ]

〇〇

原帖由 lastwinner 于 2010-11-8 00:32 发表
问题10
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
——————————————————————————————————
找出200万之内的所有素数的和


依旧是newkid的写法：
WITH t AS (
    SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM  

SQL> create or replace
  2  PROCEDURE PRIMELT(U IN NUMBER)
  3  AS
  4     TYPE t_row IS TABLE OF BINARY_INTEGER;
  5     V_RESULT T_row:=t_row();
  6     I NUMBER DEFAULT 3;
  7     J NUMBER DEFAULT 0;
  8     C NUMBER DEFAULT 2;
  9  BEGIN
10  --DBMS_PROFILER.START_PROFILER('PRIMEL');
11    v_result.EXTEND(U);
12    while(i<sqrt(U)) loop
13  if v_result(i)=1 then --利用已经计算出的质数表
14       goto n;
15     end if;
16     j:=i*(i-2);
17     while (j<U) loop
18      v_result(j):=1;
19      j:=J+i+i;
20     end loop;
21     <<n>>
22     I:=i+2;
23    end loop;
24    DBMS_OUTPUT.PUT_LINE(2);
25    for j in 1 .. U/2 loop
26  if v_result(j+j-1)is null then --只判断奇数
27  --DBMS_OUTPUT.PUT_LINE(J+j-1);
28    c:=c+j+j-1;
29    end if;
30    end loop;
31    DBMS_OUTPUT.PUT_LINE(c);
32  --DBMS_PROFILER.STOP_PROFILER;
33  END;
34  /

过程已创建。

已用时间:  00: 00: 00.03
SQL> exec primelt(2000000);
2
142913828920

PL/SQL 过程已成功完成。

已用时间:  00: 00: 01.03,不知道为什么3变成了1，结果差2

〇〇

declare
max1 number:=1;
l number:=0;
pos number:=1;
mod1 number:=1;
mod2 number:=1;
str1 varchar2(4000):='0.';
str2 varchar2(4000):='0.';
begin
for i in 1..999 loop
        if mod(i,2)=0 or mod(i,5)=0 then
                got exit1;
        end if;
        str1:='0.'||lpad('0',length(i)-1,'0');
        mod1:=power(10,length(i));
        mod2:=power(10,length(i))-1;
for j in 1..999 loop
        mod1:=mod(mod1*power(10,length(i)),i);
str1:=str1||to_char(trunc(mod2/i));
mod2:=mod(mod2,i);
if mod1=0 then
--dbms_output.put_line('有限小数i=1/'||i);
goto exit1; /*有限小数*/
end if;
if mod2=0 then
pos:=case when (j*length(i))>max1 then i else pos end;
str2:=case when (j*length(i))>max1 then str1 else str2 end;
max1:=case when (j*length(i))>max1 then (j*length(i)) else max1 end;
--dbms_output.put_line('循环小数i=1/'||i||',长度='||(j*length(i))||',str=('||substr(str1,1,200)||')');
goto exit1; /*循环小数循环节*/
end if;
--mod2:=mod2*power(10,length(i))+power(10,length(i))-1;
l:=length(mod2);
mod2:=rpad(mod2,length(i),'9');
mod2:=case when mod2>i then mod2 else mod2||'9' end;
str1:=str1||rpad(0,length(mod2)-l-1,'0');
end loop;
<<exit1>>
NULL;
end loop;
dbms_output.put_line('最长i='||pos||',长度='||length(str2)||', 0.(');
for i in 1..length(str2)/47 loop
dbms_output.put_line(substr(str2,3+(i-1)*47,47));
end loop;
dbms_output.put_line(')');
end;
/
加上红色代码，从3秒到0.7秒

〇〇

分解素数-第50题
Project Euler 第50题：

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?

这个题目约束条件很很重要，要不跑1个小时都出不了结果。从第一个素数开始，依次求最多连续的素数和。如果第N个素数和最大连续数目的乘积大于1000000，即可退出。

benben@ubuntu:~/projecteuler/50$ time python consecutive-primes-50.py
[543, 997651]

real    0m0.877s
user    0m0.830s
sys     0m0.050s

〇〇

Problem 308[size=80%]30 October 2010

A program written in the programming language Fractran consists of a list of fractions.
The internal state of the Fractran Virtual Machine is a positive integer, which is initially set to a seed value. Each iteration of a Fractran program multiplies the state integer by the first fraction in the list which will leave it an integer.
For example, one of the Fractran programs that John Horton Conway wrote for prime-generation consists of the following 14 fractions:

17 91

,

78 85

,

19 51

,

23 38

,

29 33

,

77 29

,

95 23

,

77 19

,

1 17

,

11 13

,

13 11

,

15 2

,

1 7

,

55 1

.

Starting with the seed integer 2, successive iterations of the program produce the sequence:
15, 825, 725, 1925, 2275, 425, ..., 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...
The powers of 2 that appear in this sequence are 2[img][/img]2[img][/img], 2[img][/img]3[img][/img], 2[img][/img]5[img][/img], ...
It can be shown that all the powers of 2 in this sequence have prime exponents and that all the primes appear as exponents of powers of 2, in proper order!
If someone uses the above Fractran program to solve Project Euler Problem 7 (find the 10001[img][/img]st[img][/img] prime), how many iterations would be needed until the program produces 2[img][/img]10001st prime[img][/img] ?

lastwinner

问题45： 求40755之后下一个相同的三角数、五角数和六角数

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle   Tn=n(n+1)/2   1, 3, 6, 10, 15, ...
Pentagonal   Pn=n(3n1)/2   1, 5, 12, 22, 35, ...
Hexagonal   Hn=n(2n1)   1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

—————————————————————————————————————————————————

很容易想到的方法：
with oo as (select rownum rn from dual connect by rownum<=300),
t as (select rn, rn*(rn+1)/2 tt from oo),
p as (select rn, rn*(3*rn-1)/2 pp from oo),
h as (select rn, rn*(2*rn-1) hh from oo)
select t.*, p.*, h.* from t, p, h where t.tt=p.pp and h.hh=p.pp and h.hh<(select max(tt) from t)

不过这很不靠谱，换成3000后，得好几秒才出结果

换个思路，用六角数去推三角和五角数

with oo as (select rownum+0 rn from dual connect by rownum<=30000),
h as (select rn, rn*(2*rn-1) hh from oo),
pre1 as (select h.*, trunc(sqrt(2*hh)) trn  from h),
pre2 as (select h.*, ((1+sqrt(1+4*3*(2*hh)))/(2*3)) prn  from h)
select pre1.*, pre2.prn from pre1, pre2 where trn*(trn+1)=2*pre1.hh and round(prn)=prn  and pre1.rn= pre2.rn

1s之内出结果


        RN         HH        TRN        PRN
---------- ---------- ---------- ----------
         1          1          1          1
       143      40755        285        165
     27693  1533776805      55385      31977

3 rows selected.


3000不行，多加一个0，30000，很幸运，出结果了

补充一下trn的算法
trn*(trn+1)/2=hh  => trn(trn+1)=2*hh
因为 trn^2<trn(trn+1)<(trn+1)^2
所以 trn<SQRT(2*hh)<trn+1
余下就不推了

[ 本帖最后由 lastwinner 于 2010-11-8 23:04 编辑 ]

lastwinner

问题 46：求出最小的不能表示为一个质数和一个平方数的二倍之和的奇合数。

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2*1^2
15 = 7 + 2*2^2
21 = 3 + 2*3^2
25 = 7 + 2*3^2
27 = 19 + 2*2^2
33 = 31 + 2*1^2

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

__________________________________________________________________
with oo as (select rownum*2+1 rn from dual connect by rownum<=3000 minus select pn from prime),
pre as (select rn, pn, sqrt((rn-pn)/2) sq   from oo, prime where pn<rn)
select rn from pre group by rn having  sum(decode(trunc(sq),sq,0,1))=count(*)
/


        RN
----------
      5777        --这个就是answer
      5993

2 rows selected.

5s钟，呵呵

newkid

OO的71楼算法看不懂，为什么我把循环替换为for i in 999..999 loop就算不出来呢？照理说应该把1/999的循环部分转出来啊。

newkid

辗转相除法求最小公倍数：费了半天劲才调试完，用SQL写此类算法真是自虐。

SELECT val,lcm
   FROM (SELECT *
           FROM (SELECT ROWNUM n
                       ,ROWNUM val ---- 用另外的列存放要求公倍数的值。不一定是连续的自然数
                   FROM DUAL
                 CONNECT BY ROWNUM<=20)
               ,(SELECT ROWNUM col
                   FROM DUAL
                CONNECT BY ROWNUM<=30 ---- 假设辗转相除法迭代次数不超过30
                )
         MODEL IGNORE NAV RETURN UPDATED ROWS
         DIMENSION BY (n,col)
         MEASURES (val,0 a,1 b,val lcm)
         RULES AUTOMATIC ORDER (
                a[n>1,any] order by n,col = CASE WHEN cv(col)=1 THEN val[cv(),cv()]
                                                 WHEN a[cv(),cv()-1]<>0 THEN MOD(b[cv(),cv()-1],a[cv(),cv()-1])
                                                 ELSE 0
                                            END
               ,b[n>1,any] order by n,col = CASE WHEN cv(col)=1 THEN lcm[cv()-1,30]
                                                 WHEN a[cv(),cv()-1]<>0 THEN a[cv(),cv()-1]
                                                 ELSE b[cv(),cv()-1]
                                            END
               ,lcm[n>1,any] order by n,col = lcm[cv()-1,30]*val[cv(),1]/b[cv(),cv()]
                )
         )
WHERE col=30;

       VAL        LCM
---------- ----------
         2          2
         3          6
         4         12
         5         60
         6         60
         7        420
         8        840
         9       2520
        10       2520
        11      27720
        12      27720
        13     360360
        14     360360
        15     360360
        16     720720
        17   12252240
        18   12252240
        19  232792560
        20  232792560

递归WITH写出来是这样：


WITH
t (val,a,b,lcm) AS (
  SELECT 1,0,1,1 FROM DUAL
  UNION ALL
  SELECT CASE WHEN t.a = 0 THEN t.val+1 ELSE t.val END
        ,CASE WHEN t.a = 0 THEN t.val+1
              ELSE MOD(t.b,t.a)
         END
        ,CASE WHEN t.a=0 THEN t.lcm
              ELSE t.a
         END
        ,CASE WHEN mod(t.b,t.a)=0 THEN t.lcm*t.val/t.a
              ELSE t.lcm
         END
    FROM t
   WHERE t.val<20 OR t.val=20 AND t.a<>0  ---- 比MODEL多了这个退出里层循环的方法
)
SELECT val,lcm FROM t WHERE a=0;

〇〇

原帖由 newkid 于 2010-11-9 01:37 发表
OO的71楼算法看不懂，为什么我把循环替换为for i in 999..999 loop就算不出来呢？照理说应该把1/999的循环部分转出来啊。

确实是bug,我再看看
是最后打印的循环上标差1

/*
设计思路：
如果一个数是有限小数，那么余数乘以10的n次方，总有能整除的。
比如1/8，第1步1/8余数1，第2步10/8余数2，第3步20/8余数4，第4步40/8余数0
如果一个数是循环小数，记为0.(a),a的长度是b，展开式为a*(1/10^b+1/10^2b+...10^nb)
按照等比数列求和公式0.(a)=a*(1-q^n)/(1-q),当n趋向无穷，等于a/(1-q)=a/(1-1/10^b)
=a*10^b/(a^b-1),因此可以断定:长度为b的连续9组成的数一定能被a整除。
比如1/7=0.(142857),142857=999999/7,
另外，分母*2或者*5不影响循环节长度，比如1/3=0.(3),1/6=0.1(6),1/15=0.0(6),
因此可以忽略分母能被2，5整除的那些数。
实现：穷举法，对每个分母i，分别计算
余数1=10^n /i 的余数，下个余数*10
余数2=(10^n-1) /i 的余数,下个余数*10+9,例如:9/7->29/7->19/7->59/7->39/7->49/7
任何一个余数如果为0表示整除或者一轮循环节结束。
*/

declare
max1 number:=1;
l number:=0;
pos number:=1;
mod1 number:=1;
mod2 number:=1;
str1 varchar2(4000):='0.';
str2 varchar2(4000):='0.';
begin
for i in 999..999 loop
        if mod(i,2)=0 or mod(i,5)=0 then
                goto exit1;
        end if;
        str1:='0.'||lpad('0',length(i)-1,'0');
        mod1:=power(10,length(i));
        mod2:=power(10,length(i))-1;
for j in 1..999 loop
        mod1:=mod(mod1*power(10,length(i)),i);
str1:=str1||to_char(trunc(mod2/i));
mod2:=mod(mod2,i);
if mod1=0 then
--dbms_output.put_line('有限小数i=1/'||i);
goto exit1; /*有限小数*/
elsif mod2=0 then
pos:=case when (j*length(i))>max1 then i else pos end;
str2:=case when (j*length(i))>max1 then str1 else str2 end;
max1:=case when (j*length(i))>max1 then (j*length(i)) else max1 end;
--dbms_output.put_line('循环小数i=1/'||i||',长度='||(j*length(i))||',str=('||substr(str1,1,200)||')');
goto exit1; /*循环小数循环节*/
end if;
l:=length(mod2);
mod2:=rpad(mod2,length(i),'9');
mod2:=case when mod2>i then mod2 else mod2||'9' end;
str1:=str1||rpad(0,length(mod2)-l-1,'0');
end loop;
<<exit1>>
NULL;
end loop;
dbms_output.put_line('最长i='||pos||',长度='||length(str2)||', 0.(');
for i in 1..length(str2)/47+1 loop
dbms_output.put_line(substr(str2,3+(i-1)*47,47));
end loop;
dbms_output.put_line(')');
end;
/

[ 本帖最后由 〇〇 于 2010-11-9 09:10 编辑 ]