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

tree_new_bee

改成Plsql:

declare
i number; j number;
cons number;
icopy number;
k number;
factors number;
cnt number;
begin
  cons:=0;
  i:= 2;
  while 1=1 loop
        factors:=0;
        cnt := 0;
        icopy := i;
        j := 2;
        while j<i and j<=icopy loop
            while mod(icopy,j) = 0 loop
               icopy := icopy/j;
               cnt:=1;
            end loop;
            factors:=factors+cnt;
           cnt:=0;
           if j>2 then j:=j+2; else j:=j+1; end if;
        end loop;
        if factors = 4 then
          cons := cons+1;
          if cons = 4 then
            dbms_output.put_line('first number:'|| (i-3));
            return;
          end if;
        else
          cons := 0;
        end if;
        i:= i+1;   
  end loop;
end;

first number:134043

PL/SQL procedure successfully completed

Executed in 810.109 seconds

比起上面的SQL是快多了， 但还是要10多分钟， 太慢！

[ 本帖最后由 tree_new_bee 于 2010-12-28 23:49 编辑 ]

tree_new_bee

把21/22题的成果充分利用起来， 另外加上#110楼里newkid提到的j用质数表来循环：

declare
i number; j number;
cons number;
icopy number;
k number;
factors number;
cnt number;
primlist t_numlist;
begin
  primlist:=pkg_prim2.seive_numlist(100000);
  cons:=0;
  i:= 2;
  while 1=1 loop
        factors:=0;
        cnt := 0;
        icopy := i;
        k := primlist.first;
        j := primlist(k);
        while j*j<=icopy loop
            while j<=icopy and mod(icopy,j) = 0 loop
               icopy := icopy/j;
               cnt:=1;
            end loop;
            factors:=factors+cnt;
           cnt:=0;
           k := primlist.next(k);
           j:=primlist(k);
        end loop;
        if icopy > 1 then factors:=factors+1; end if;
        if factors = 4 then
          cons := cons+1;
          if cons = 4 then
            dbms_output.put_line('first number:'|| (i-3));
            return;
          end if;
        else
          cons := 0;
        end if;
        i:= i+1;   
  end loop;
end;

first number:134043

PL/SQL procedure successfully completed

Executed in 4.25 seconds


这个结果应该算是令人满意。

newkid

我说哥们，这些就算第一季吧？楼搭太高，后面的页都进不了搜索引擎。

tree_new_bee

原帖由 newkid 于 2010-12-29 07:28 发表
我说哥们，这些就算第一季吧？楼搭太高，后面的页都进不了搜索引擎。

哦。
那就做到第50题，换新楼。

tree_new_bee

Q48  Find the last ten digits of 11 + 22 + ... + 10001000.

The series, 1^(1) + 2^(2) + 3^(3) + ... + 10^(10) = 10405071317.

Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000).

tree_new_bee

48题看似简单， 但即使用上了大数幂， 依然并不轻松。

下面的SQL:
with t as (select level n from dual where mod(level,10) >0 connect by level<=200)
,tp as (select /*+ MATERIALIZE */ pkg_bignum.bigpower(n,n) np from t)
select substr(sum( case when length(np)>10 then substr(np,-10) else np end),-10) from tp

SUBSTR(SUM(CASEWHENLENGTH(NP)>
------------------------------
6339403340

Executed in 12.438 seconds

在计算到100的时候只要1秒多，200的时候要12秒， 300的时候要45秒。 500的时候已经要238秒了！


问题出在当大数的位数很大时， 大数乘法的效率非常低。 比如说计算bigpower(999,999):
PKG_BIGNUM.BIGPOWER(999,999)
--------------------------------------------------------------------------------
36806348825922326789470084006052186583833823203735320465595962143702560930047223

Executed in 10.062 seconds

计算这一个数就要10秒，光是计算这1000个数的幂， 估计就要以小时算了。

[ 本帖最后由 tree_new_bee 于 2010-12-29 12:15 编辑 ]

tree_new_bee

因此， 要在计算幂的时候，就把位数截断， 每次乘的结果只保留最后10位。
为之前的大数运算package增加下面的函数：

  function bigpower10(d1 varchar2, n number) return varchar2 is --只保留最后10位数
    result varchar2(30000);
  begin
    result := '1';
    for i in 1 .. n loop
      result := bigmulti(result, d1);
      if length(result)>10 then result := substr(result,-10); end if;
    end loop;
    return result;
  end;


这样计算起幂来， 效率高多了：
select pkg_bignum.bigpower10(999,999) from dual;

PKG_BIGNUM.BIGPOWER10(999,999)
--------------------------------------------------------------------------------
0499998999

Executed in 0.125 seconds

SQL>

[ 本帖最后由 tree_new_bee 于 2010-12-29 12:16 编辑 ]

tree_new_bee

用上上面的函数后， 就轻松一些了。

with t as (select level n from dual where mod(level,10) >0 connect by level<=1000)
select substr(sum(pkg_bignum.bigpower10(n,n)),-10) from t

SUBSTR(SUM(PKG_BIGNUM.BIGPOWER
------------------------------
9110846700

Executed in 28.234 seconds

SQL>

虽说依然要半分钟，不算快， 但已经可以接受了。

tree_new_bee

另外，我的大数幂运算函数，有一点不足：
每次都是一个一个的相乘， 效率比较低。
如果改成两个两个的乘， 然后结果再相乘， 。。。
比如说power(n, 7)
先计算n*n
然后 (n*n) * (n*n)
然后 ((n*n) * (n*n)) * (n*n)
最后再乘以一个n
这样只要乘4次就可以得到结果， 而不是像原来那样乘6次。


这样效率一定能高许多。  不过想起来就觉得麻烦的头疼， 有兴趣的朋友可以尝试尝试。

tree_new_bee

Q49 Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other.

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?