Project Euler Problem 276, 268, 347

〇〇

Problem 276[size=80%]29 January 2010

Consider the triangles with integer sides a, b and c with a b c.
An integer sided triangle (a,b,c) is called primitive if gcd(a,b,c)=1.
How many primitive integer sided triangles exist with a perimeter not exceeding 10 000 000?

newkid

我把另外两个搬过来并删掉原贴。这些东西就是玩玩，不是本版主旋律。

Problem 268 11 December 2009

It can be verified that there are 23 positive integers less than 1000 that are divisible by at least four distinct primes less than 100.
Find how many positive integers less than 10^16 are divisible by at least four distinct primes less than 100.

newkid

Problem 347  03 September 2011

The largest integer  100 that is only divisible by both the primes 2 and 3 is 96, as 96=32*3=25*3. For two distinct primes p and q let M(p,q,N) be the largest positive integer N only divisible by both p and q and M(p,q,N)=0 if such a positive integer does not exist.
E.g. M(2,3,100)=96.
M(3,5,100)=75 and not 90 because 90 is divisible by 2 ,3 and 5.
Also M(2,73,100)=0 because there does not exist a positive integer  100 that is divisible by both 2 and 73.
Let S(N) be the sum of all distinct M(p,q,N). S(100)=2262.
Find S(10 000 000).

newkid

后两个看起来比较容易，就是对数+组合。

newkid

#347, 他说S(100)=2262, 我算出来只是2242, 哪里有错？

VAR N NUMBER;
EXEC :N := 100;

WITH
t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= CEIL(((:n)/2-1-1)/2)
    )
,p AS (
SELECT pn,LOG(10,pn) lg
FROM (
      SELECT rn pn from t
      MINUS
      SELECT t1.rn * t2.rn
        FROM t t1, t t2
      WHERE t1.rn <= t2.rn
            AND t1.rn <=SQRT(:n)
            AND t1.rn * t2.rn <:n/2
      UNION ALL SELECT 2 FROM DUAL
      )
)
,lg AS (
SELECT p1.pn pn1, p1.lg lg1, p2.pn pn2, p2.lg lg2
  FROM p p1,p p2
WHERE p1.pn<p2.pn AND p1.lg+p2.lg<=LOG(10,:n)
)
SELECT SUM(max_p)
  FROM (
SELECT lg.*
      ,(SELECT MAX(POWER(pn1,FLOOR((LOG(10,:N)-LEVEL*lg2)/lg1))*POWER(pn2,LEVEL))
         FROM DUAL
        CONNECT BY LEVEL<=FLOOR((LOG(10,:N)-lg1)/lg2)
        ) max_p
  FROM lg
)
/


SUM(MAX_P)
----------
      2242



WITH
t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= CEIL(((:n)/2-1-1)/2)
    )
,p AS (
SELECT pn,LOG(10,pn) lg
FROM (
      SELECT rn pn from t
      MINUS
      SELECT t1.rn * t2.rn
        FROM t t1, t t2
      WHERE t1.rn <= t2.rn
            AND t1.rn <=SQRT(:n)
            AND t1.rn * t2.rn <:n/2
      UNION ALL SELECT 2 FROM DUAL
      )
)
,lg AS (
SELECT p1.pn pn1, p1.lg lg1, p2.pn pn2, p2.lg lg2
  FROM p p1,p p2
WHERE p1.pn<p2.pn AND p1.lg+p2.lg<=LOG(10,:n)
)
SELECT (SELECT MAX(LPAD(POWER(pn1,FLOOR((LOG(10,:N)-LEVEL*lg2)/lg1))*POWER(pn2,LEVEL),3)||'='||pn1||'^'||FLOOR((LOG(10,:N)-LEVEL*lg2)/lg1)||' * '||pn2||'^'||LEVEL)
         FROM DUAL
        CONNECT BY LEVEL<=FLOOR((LOG(10,:N)-lg1)/lg2)
        ) max_p
  FROM lg
/

展开：
MAX_P
--------------------
96=2^5 * 3^1
80=2^4 * 5^1
98=2^1 * 7^2
88=2^3 * 11^1
52=2^2 * 13^1
68=2^2 * 17^1
76=2^2 * 19^1
92=2^2 * 23^1
58=2^1 * 29^1
62=2^1 * 31^1
74=2^1 * 37^1
82=2^1 * 41^1
86=2^1 * 43^1
94=2^1 * 47^1
75=3^1 * 5^2
63=3^2 * 7^1
99=3^2 * 11^1
39=3^1 * 13^1
51=3^1 * 17^1
57=3^1 * 19^1
69=3^1 * 23^1
87=3^1 * 29^1
93=3^1 * 31^1
35=5^1 * 7^1
55=5^1 * 11^1
65=5^1 * 13^1
85=5^1 * 17^1
95=5^1 * 19^1
77=7^1 * 11^1
91=7^1 * 13^1

30 rows selected.

用SQL造素数表比较慢，即使把前几个已知素数手工加入也不怎么样。
后面求最大值用的是穷尽法，这也比较笨，100万都得花四分多钟。哪位学过立体解析几何的给个公式。

〇〇

newkid 发表于 2012-1-7 06:14
#347, 他说S(100)=2262, 我算出来只是2242, 哪里有错？

VAR N NUMBER;

展开：
MAX_P
--------------------
80=2^4 * 5^1

===>
100=2^2 * 5^2

newkid

原来是误差搞鬼，加个 ROUND(,30)

VAR N NUMBER;
EXEC :N := 100;

WITH
t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= CEIL(((:n)/2-1-1)/2)
     )
,p AS (
SELECT pn,LOG(10,pn) lg
FROM (
       SELECT rn pn from t
       MINUS
       SELECT t1.rn * t2.rn
         FROM t t1, t t2
       WHERE t1.rn <= t2.rn
             AND t1.rn <=SQRT(:n)
             AND t1.rn * t2.rn <:n/2
       UNION ALL SELECT 2 FROM DUAL
       )
)
,lg AS (
SELECT p1.pn pn1, p1.lg lg1, p2.pn pn2, p2.lg lg2
   FROM p p1,p p2
WHERE p1.pn<p2.pn AND p1.lg+p2.lg<=LOG(10,:n)
)
SELECT SUM(max_p)
   FROM (
SELECT lg.*
       ,(SELECT MAX(POWER(pn1,FLOOR(ROUND((LOG(10,:N)-LEVEL*lg2)/lg1,30)))*POWER(pn2,LEVEL))
          FROM DUAL
         CONNECT BY LEVEL<=FLOOR((LOG(10,:N)-lg1)/lg2)
         ) max_p
   FROM lg
)
/

SUM(MAX_P)
----------
      2262

lastwinner

应该考虑如何利用Oracle和其他开发语言，发挥各自优势，达到最快解决问题的目的。
btw：支持合并，以后这类东西在一个帖子里玩就行，记得之前我们就是这么玩的

〇〇

268
借助newid的代码

WITH
t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= CEIL(((:n)/2-1-1)/2)
    )
,p AS (
SELECT pn,LOG(10,pn) lg
FROM (
SELECT 2 pn FROM DUAL
UNION ALL
      SELECT rn pn from t
      MINUS
      SELECT t1.rn * t2.rn
        FROM t t1, t t2
      WHERE t1.rn <= t2.rn
            AND t1.rn <=SQRT(:n)
            AND t1.rn * t2.rn <:n/2
      )
)
,k as (select level l from dual connect by level<=1000)
select count(unique l) from k,p p1,p p2,p p3,p p4
where mod(l,p1.pn) =0 and
mod(l,p2.pn) =0 and mod(l,p3.pn) =0 and mod(l,p4.pn) =0
and p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn;

〇〇

这样不用unique
WITH
t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= CEIL(((:n)/2-1-1)/2)
    )
,p AS (
SELECT pn,LOG(10,pn) lg
FROM (
SELECT 2 pn FROM DUAL
UNION ALL
      SELECT rn pn from t
      MINUS
      SELECT t1.rn * t2.rn
        FROM t t1, t t2
      WHERE t1.rn <= t2.rn
            AND t1.rn <=SQRT(:n)
            AND t1.rn * t2.rn <:n/2
      )
)
,k as (select level l from dual connect by level<=1000)
select count(l) from k where exists(select 1 from p p1,p p2,p p3,p p4
where mod(l,p1.pn) =0 and
mod(l,p2.pn) =0 and mod(l,p3.pn) =0 and mod(l,p4.pn) =0
and p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn);