sql求解200万内质数各种算法点评

〇〇 · 发表于 2014-3-11 20:37

貌似改为直接函数调用也没事

SQL> with
  2  t0 AS (
  3    SELECT 2*level+1 rn FROM dual connect by level <= (:n)/2-1 --原SQL为(:n)/2-1-1有误，特做此更正——by lastwinner
  4    ),
  5  t as(SELECT rn from t0 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0 and mod(rn,11)<>0 and mod(rn,13)<>0 and mod(rn,17)<>0 and mod(rn,19)<>0)
  6  SELECT COUNT(*)+1+7 --2，3，5，7，11，13，17，19
  7    FROM (SELECT rn from t
  8          MINUS
  9          SELECT t1.rn * t2.rn
10          FROM t t1, t t2
11          WHERE t1.rn <= t2.rn
12                AND t1.rn BETWEEN 21 AND SQRT(:n)
13                AND t1.rn * t2.rn <:n
14       )
15  ;

COUNT(*)+1+7--2，3，5，7，11，13，17，19
----------------------------------------
                              148933

已用时间:  00: 00: 16.22

执行计划
----------------------------------------------------------
Plan hash value: 2858566071

-------------------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name                   | Rows  | Bytes | Cost (%CPU)| Time    |
-------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT             |                         |    1 |    |    8 (0)| 00:00:01 |
| 1 |  TEMP TABLE TRANSFORMATION    |                         |    |    |          |       |
| 2 | LOAD AS SELECT             | SYS_TEMP_0FD9D6618_C88BEC |    |    |          |       |
|*  3 | VIEW                      |                         |    1 | 13 |    2 (0)| 00:00:01 |
|*  4 |    CONNECT BY WITHOUT FILTERING|                         |    |    |          |       |
| 5 |    FAST DUAL                |                         |    1 |    |    2 (0)| 00:00:01 |
| 6 | SORT AGGREGATE             |                         |    1 |    |          |       |
| 7 | VIEW                      |                         |    1 |    |    6 (0)| 00:00:01 |
| 8 |    MINUS                      |                         |    |    |          |       |
| 9 |    SORT UNIQUE             |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  10 |    VIEW                   |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  11 |       TABLE ACCESS FULL       | SYS_TEMP_0FD9D6618_C88BEC |    1 | 13 |    2 (0)| 00:00:01 |
|  12 |    SORT UNIQUE             |                         |    1 | 26 |    4 (0)| 00:00:01 |
|* 13 |    FILTER                   |                         |    |    |          |       |
|  14 |       NESTED LOOPS          |                         |    1 | 26 |    4 (0)| 00:00:01 |
|* 15 |       VIEW                   |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  16 |       TABLE ACCESS FULL    | SYS_TEMP_0FD9D6618_C88BEC |    1 | 13 |    2 (0)| 00:00:01 |
|* 17 |       VIEW                   |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  18 |       TABLE ACCESS FULL    | SYS_TEMP_0FD9D6618_C88BEC |    1 | 13 |    2 (0)| 00:00:01 |
-------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

3 - filter(MOD("RN",3)<>0 AND MOD("RN",5)<>0 AND MOD("RN",7)<>0 AND MOD("RN",11)<>0 AND
            MOD("RN",13)<>0 AND MOD("RN",17)<>0 AND MOD("RN",19)<>0)
4 - filter(LEVEL<=TO_NUMBER(:N)/2-1)
  13 - filter(SQRT(TO_NUMBER(:N))>=21)
  15 - filter("T1"."RN">=21 AND "T1"."RN"<=SQRT(TO_NUMBER(:N)))
  17 - filter("T1"."RN"<="T2"."RN" AND "T1"."RN"*"T2"."RN"<TO_NUMBER(:N) AND "T2"."RN">=21)

统计信息
----------------------------------------------------------
      13  recursive calls
      535  db block gets
   124484  consistent gets
      520  physical reads
      660  redo size
      381  bytes sent via SQL*Net to client
      472  bytes received via SQL*Net from client
      2  SQL*Net roundtrips to/from client
      3  sorts (memory)
      0  sorts (disk)
      1  rows processed

编程小强 · 发表于 2014-3-11 21:58

学习。。。

lastwinner · 发表于 2014-3-12 01:08

〇〇发表于 2014-3-11 20:15
这个写法是故意的吗？
AND (SELECT SQRT(:n) FROM DUAL)

可以直接写为SQRT(:n)
我比较过，时间上没差别

binyong119 · 发表于 2014-3-12 11:21

helonten 发表于 2014-3-10 08:27
这种分析问题的方法非常值得我们学习

学习了啊，值得学习

lastwinner · 发表于 2014-3-19 02:20

增加了“8、分段求解”，详见8楼

lastwinner · 发表于 2014-3-19 02:24

lastwinner 发表于 2014-3-10 04:04
8、分段求解
虽然sql没法像pl/sql那样有效的利用之前的计算结果，但部分做到还是可行的吧？我们来尝试一下 ...

但newkid的写法不能使用此思路，想想看为什么？

如果没想出来，那么看看如下的sql，其中 :n 赋值为400000，看看输出结果，就能大概想明白了
with b as (select 1 r from dual union all select 2 from dual),
c as (select rownum from b,b,b,b,b),
d as (select rownum from c,c,c,c),
e as (select rownum rn from d), --只需要一半
t0 AS (
SELECT 2*rn+1 rn FROM e where rn <= (:n)/2-1 --原SQL为(:n)/2-1-1有误，特做此更正——by lastwinner
),
t1 as(SELECT rn from t0 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0 and mod(rn,11)<>0 and mod(rn,13)<>0 and mod(rn,17)<>0 and mod(rn,19)<>0),
u1 as (select rn from t1 where rn<=sqrt(:n)),
u2 as (select rn from t1 where rn>sqrt(:n) and rn<=:n),
v1 as (SELECT rn from u1
      MINUS
      SELECT t1.rn * t2.rn
         FROM u1 t1, u1 t2
      WHERE t1.rn <= t2.rn
            AND t1.rn BETWEEN 21 AND sqrt(SQRT(:n))+1
            AND t1.rn * t2.rn <=sqrt(:n)+1),
u3 as (select * from u2 union select * from v1),
v2 as (SELECT rn from u2
      MINUS
      SELECT t1.rn * t2.rn
         FROM v1 t1, u3 t2
      WHERE t1.rn <= t2.rn
            AND t1.rn BETWEEN 21 AND SQRT(:n)
            AND
            t1.rn * t2.rn <=:n)
, u as (select rn n from t1)
, z as (select * from u minus
select * from u a where exists (select /*+ USE_MERGE (a b)*/ 0 from u b where b.n<=sqrt(a.n) and mod(a.n, b.n)=0))
select * from v2 minus select * from z
/