puzzleup2012谜题，请用SQL或PLSQL解答

lastwinner

newkid 发表于 2012-10-17 23:45
#13 Double Factored

Let's call a number "double factored" if at least one of its prime factors re ...

如果一个数，它的某个质数因子在分解的时候重复出现，则称之为“重因子”数。最小的连同四个相邻数都是“重因子”数的整数是多少？（四个相邻数只的是：前两个数，该数本身，后两个数）

如果问题问的是两个相邻数（前一个，该数本身，后一个）那么答案为 49 (48=2x2x2x2x3 , 49=7x7, 50=2x5x5)
————————————————————————————————
我觉得你翻译得有歧义，应该这样更好
如果一个数，它的某个质数因子在分解的时候重复出现，则称之为“重因子”数。如果一个正整数和它的四个邻居（两个在前，该数本身，两个在后）都是“重因子”数，那么这个数最小是多少？如果问题问的是一个正整数和它的两个邻居，那么这个数是49(48=2x2x2x2x3 , 49=7x7, 50=2x5x5).

lastwinner

newkid 发表于 2012-10-18 01:29
13题果然在很小的范围内，用筛法一下子就求出来了。

with t as (select 4 a from dual union select 9 from dual union select 25 from dual union select 49 from dual union select 121 from dual union select 169 from dual ),
n as (select rownum r from dual connect by rownum<=250),--只在1000之内查找
i as (select distinct a*r p from t,n where a*r<=1000),
r as (select p, p-rank()over(order by p) g from i)
select min(p), max(p), count(*) from r group by g having count(*)>=5

运气真好，居然一下就找到了
844        848        5
说明846是答案

不过，由于答案超过了预设的13*13=169，所以有必要重新修改sql以验证这个答案是否真的是最终结果

lastwinner

lastwinner 发表于 2012-10-18 02:31
with t as (select 4 a from dual union select 9 from dual union select 25 from dual union select 49 ...

with t as (select 4 a from dual union select 9 from dual union select 25 from dual union select 49 from dual union select 121 from dual union
           select 169 from dual union select 289 a from dual union select 361 from dual union select 529 from dual union select 841 from dual),
n as (select rownum r from dual connect by rownum<=250),--只在1000之内查找
i as (select distinct a*r p from t,n where a*r<=1000),
r as (select p, p-rank()over(order by p) g from i)
select min(p), max(p), count(*) from r group by g having count(*)>=5

结果还是846

lastwinner

尝试了一下找6个的
with t as (select 4 a from dual union select 9 from dual union select 25 from dual union select 49 from dual union select 121 from dual union
           select 169 from dual union select 289 a from dual union select 361 from dual union select 529 from dual union select 841 from dual),
n as (select rownum r from dual connect by rownum<=12500),--只在1000之内查找
i as (select distinct a*r p from t,n where a*r<=50000),
r as (select p, p-rank()over(order by p) g from i)
select min(p), max(p), count(*) from r group by g having count(*)>=6
————————————————————————————————————————
结果有俩
22020        22025        6
47672        47677        6


当然，不能保证这就是最小的结果。

————————————————————————————————————————————————————
这个问题，如果用筛除，应该会效率更高，毕竟在剔除所有的质数和任意两个质数的乘积后，只需要从剩下的数中找出最小的连续N个数，就一定是满足题设要求的答案了

newkid

呵呵，殊途同归，我是从以前的PLSQL程序改的：

DECLARE
   TYPE t_row IS TABLE OF  BINARY_INTEGER;

   V_RESULT T_row:=t_row();
   V_RESULT2 T_row:=t_row();
   
   I NUMBER DEFAULT 1;
   J NUMBER DEFAULT 0;
   C NUMBER DEFAULT 1;
   
   lv_limit NUMBER := 1e5;
   
   lv_upper1 NUMBER := SQRT(lv_limit);
   
   lv_step BINARY_INTEGER;
BEGIN
    v_result.EXTEND(lv_limit);
    v_result2.EXTEND(lv_limit);
   
    v_result.DELETE(1);
    i:=2;
    while i<=lv_upper1 loop
          lv_step := i*i;
          j := lv_step;
          while j<=lv_limit loop
                j:=j+lv_step;
                v_result2.DELETE(j);
          end loop;

          j:=i*2;
          while j<=lv_limit loop
                v_result.DELETE(j);
                j:=j+i;
          end loop;
          i := v_result.NEXT(i);
    end loop;
   
    j := v_result2.NEXT(3);
    WHILE j>0 LOOP
       IF v_result2.NEXT(j) - j >5 THEN
          DBMS_OUTPUT.PUT_LINE(j+3);
          EXIT;
       END IF;
       j := v_result2.NEXT(j);
    END LOOP;

END;
/

〇〇

newkid 发表于 2012-10-17 23:45
#13 Double Factored

Let's call a number "double factored" if at least one of its prime factors re ...

终于见到一个sql好懂的题了

udfrog

嗯，差不多

1. with df as (
   
2. select (rownum+1)*(rownum+1) df from dual connect by rownum<=20),
   
3. t as (
   
4. select rownum f from dual connect by rownum<=1000),
   
5. tmp as (
   
6. select        min(df*f) keep (dense_rank first order by df*f) r, row_number() over (order by df*f) rn
   
7. from        df, t
   
8. group by df*f)
   
9. select        min(a.r)-2
   
10. from        tmp a, tmp b
    
11. where        a.r=b.r+4
    
12. and        a.rn=b.rn+4;

复制代码

udfrog

lastwinner 发表于 2012-10-18 02:39
尝试了一下找6个的
with t as (select 4 a from dual union select 9 from dual union select 25 from dua ...

“这个问题，如果用筛除，应该会效率更高，毕竟在剔除所有的质数和任意两个质数的乘积后”
这是不够的，质数与合数的乘积仍然未必满足。
而且，这样的筛除操作是：无限集a-无限集b=无限集c，再从c里面选最小的，这必须出不来结果。

lastwinner

udfrog 发表于 2012-10-18 13:53
“这个问题，如果用筛除，应该会效率更高，毕竟在剔除所有的质数和任意两个质数的乘积后”
这是不够的， ...

嗯，应该是若干质数的乘积，我疏忽了

newkid

我的筛法有两个筛子，一个找素数一个找平方数，所以是不会遗漏的。

再优化一下，第二个筛眼足够大时没有必要往前挖：

DECLARE
   TYPE t_row IS TABLE OF  BINARY_INTEGER;

   V_RESULT T_row:=t_row();
   V_RESULT2 T_row:=t_row();
   
   I NUMBER DEFAULT 1;
   J NUMBER DEFAULT 0;
   
   lv_limit NUMBER := 2e6;
   
   lv_upper1 NUMBER := SQRT(lv_limit);
   
   lv_step BINARY_INTEGER;
   lv_found NUMBER := 0;
   lv_cnt NUMBER := 8;
BEGIN
    v_result.EXTEND(lv_limit);
    v_result2.EXTEND(lv_limit);
   
    v_result.DELETE(1);
    i:=2;
    while i<=lv_upper1 loop
          lv_step := i*i;
          j := lv_step;
          while j<=lv_limit loop
                j:=j+lv_step;
                IF v_result2.EXISTS(j) THEN
                   v_result2.DELETE(j);
                   IF v_result2.NEXT(j) - v_result2.PRIOR(j) >= lv_cnt+1 THEN
                      IF v_result2.PRIOR(j)<lv_found OR lv_found=0 THEN
                         lv_found := v_result2.PRIOR(j);
                         lv_limit := lv_found;
                         lv_upper1 := LEAST(lv_upper1,lv_found);
                      END IF;
                      EXIT;
                   END IF;
                END IF;
          end loop;

          j:=i*(i-1);
          while j<=lv_limit loop
                v_result.DELETE(j);
                j:=j+i;
          end loop;
          i := v_result.NEXT(i);
    end loop;
   
    IF lv_found>0 THEN
       DBMS_OUTPUT.PUT_LINE(lv_found+1);
    END IF;
END;
/

1092747
这是二百万内找连续8个的。