求200万以内质数的个数

newkid

排除越多就越快：
WITH t0 AS (
    SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/2-1-1
    ),
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
            and mod(rn,23)<>0
            and mod(rn,29)<>0
    )
SELECT COUNT(*)+10 --2,3,5,7,11,13,17,19,23,29
   FROM (SELECT rn from t
         MINUS
         SELECT t1.rn * t2.rn
           FROM t t1, t t2
         WHERE t1.rn <= t2.rn
               AND t1.rn BETWEEN 31 AND (SELECT SQRT(:n) FROM DUAL)
               AND t1.rn * t2.rn <:n
       )
/

COUNT(*)+10--2,3,5,7,11,13,17,19,23,29
--------------------------------------
                                148933

Elapsed: 00:00:17.30
我就是用很普通的笔记本。

〇〇

续集
http://www.itpub.net/thread-1315113-1-1.html

〇〇

原帖由 newkid 于 2009-12-10 04:38 发表
再把偶数除掉，现在差不多半秒：
WITH t AS (
   SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 10000-1
   )
,t_odd AS (
   SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 10000-1
   )
SELECT COUNT(*)+1
  FROM (SELECT rn from t_odd
        MINUS
        SELECT t1.rn * t2.rn
          FROM t t1, t t2
         WHERE t1.rn <= t2.rn
               AND t1.rn <= (SELECT SQRT(20000) FROM DUAL)
               AND t1.rn * t2.rn <20000
       )
/

COUNT(*)+1
----------
      2262

Elapsed: 00:00:00.45

我把你的2改成3，又缩短1半

SQL> var N number;
SQL> exec :N:=20000;

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> with t as
  2  (select level*2+1 l from dual connect by level<=:N/2),
  3  t1 as (select level*2+1 l from dual connect by level<=:N/3)
  4  ,p1k as(select * from t
  5  minus
  6  select t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(:N)
  7  and t1.l<=t2.l and t1.l*t2.l<=:N
  8  )
  9  select count(*) from p1k;

  COUNT(*)
----------
      2262

已用时间:  00: 00: 00.13
SQL> WITH t AS (
  2     SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 10000-1
  3     )
  4  ,t_odd AS (
  5     SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 10000-1
  6     )
  7  SELECT COUNT(*)+1
  8    FROM (SELECT rn from t_odd
  9          MINUS
10          SELECT t1.rn * t2.rn
11            FROM t t1, t t2
12           WHERE t1.rn <= t2.rn
13                 AND t1.rn <= (SELECT SQRT(20000) FROM DUAL)
14                 AND t1.rn * t2.rn <20000
15         )
16  /

COUNT(*)+1
----------
      2262

已用时间:  00: 00: 00.31

〇〇

100万怎么优化也不够

SQL> exec :n:=1000000

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> with t as
  2  (select level*6+1 l from dual connect by level<=:N/6
  3  union all
  4  select level*6+5 l from dual connect by level<=:N/6
  5  )
  6  ,p1k as(select * from t
  7  minus
  8  select t1.l*t2.l from t t1,t t2 where t1.l<=sqrt(:N)
  9  and t1.l<=t2.l and t1.l*t2.l<=:N
10  minus
11  select level*5 from dual connect by level<=:N/5
12  )
13  select count(*) from p1k;

  COUNT(*)
----------
     78496

已用时间:  00: 00: 23.42
SQL> with t as
  2  (select level*2+1 l from dual connect by level<=:N/2),
  3  t1 as (select level*2+1 l from dual connect by level<=:N/3)
  4  ,p1k as(select * from t
  5  minus
  6  select t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(:N)
  7  and t1.l<=t2.l and t1.l*t2.l<=:N
  8  )
  9  select count(*) from p1k;

  COUNT(*)
----------
     78498

已用时间:  00: 00: 28.06

〇〇

数据有点差错,但性能提高了很多
SQL> with t as
  2  (select level*6+1 l from dual connect by level<=:N/6
  3  union all
  4  select level*6+5 l from dual connect by level<=:N/6
  5  )
  6  ,p1k as(select * from t
  7  minus
  8  select t1.l*t2.l from t t1,t t2 where t1.l<=sqrt(:N)
  9  and t1.l<=t2.l and t1.l*t2.l<=:N and t2.l<=:N/11
10  minus
11  select level*5 from dual connect by level<=:N/5
12  minus
13  select level*7-7 from dual connect by level<=:N/7
14  )
15  select count(*) from p1k;

  COUNT(*)
----------
     78495

已用时间:  00: 00: 04.47

〇〇

原帖由 newkid 于 2009-12-10 05:00 发表
200万以内的：4.5分钟

WITH t AS (
   SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/2-1
   )
,t_prime AS (
   SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/2-1
   UNION ALL
   SELECT 2 FROM DUAL
   )
SELECT COUNT(*)
  FROM (SELECT rn from t_prime
        MINUS
        SELECT t1.rn * t2.rn
          FROM t t1, t t2
         WHERE t1.rn <= t2.rn
               AND t1.rn <= (SELECT SQRT(:n) FROM DUAL)
               AND t1.rn * t2.rn <:n
       )
/


  COUNT(*)
----------
    148933

Elapsed: 00:04:27.14

SQL> var N number;
SQL> exec :N:=2000000;

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> with t as
  2  (select level*6+1 l from dual connect by level<=:N/6
  3  union all
  4  select level*6+5 l from dual connect by level<=:N/6
  5  )
  6  ,p1k as(select * from t
  7  minus
  8  select t1.l*t2.l from t t1,t t2 where t1.l<=sqrt(:N)
  9  and t1.l<=t2.l and t1.l*t2.l<=:N and t2.l<=:N/19
10  minus
11  select level*5 from dual connect by level<=:N/5
12  minus
13  select level*7+7 from dual connect by level<=:N/7
14  minus
15  select level*11+11 from dual connect by level<=:N/11
16  minus
17  select level*13+13 from dual connect by level<=:N/13
18  minus
19  select level*17+17 from dual connect by level<=:N/17
20  )
21  select count(*) from p1k;

  COUNT(*)
----------
    148931

已用时间:  00: 00: 09.24

〇〇

利用已经算出的sqrt(n)的质数表，再减少1点点
如果不用merge 提示，则执行计划变为nested loops,时间变回28秒
with t0 as
(select level*2+1 l from dual connect by level<=sqrt(:N)/2),
t1 as (select level*2+1 l from dual connect by level<=sqrt(:N)/3)
,p1k as(select l from t0
minus
select t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(sqrt(:N))
and t1.l<=t2.l and t1.l*t2.l<=:N
)
,t as
(select level*6+1 l from dual connect by level<=:N/6
union all
select level*6+5 l from dual connect by level<=:N/6
)
,p2m as(select l from t
minus
select /*+ USE_MERGE (t1 t2) */ t1.l*t2.l from p1k t1,t t2 where t1.l<=sqrt(:N)
and t1.l<=t2.l and t1.l*t2.l<=:N and t2.l<=:N/19
minus
select level*5 from dual connect by level<=:N/5
minus
select level*7+7 from dual connect by level<=:N/7
minus
select level*11+11 from dual connect by level<=:N/11
minus
select level*13+13 from dual connect by level<=:N/13
minus
select level*17+17 from dual connect by level<=:N/17
)
select count(*) from p2m;

UNT(*)
------
148931

时间:  00: 00: 07.05

〇〇

把newkid21楼加上and t2.rn<=:n/31
和use merge提示，不可思议的结果 看来mod的时间复杂度没比乘法差多少
SQL> WITH t0 AS (
  2      SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/2-1-1
  3      ),
  4  t as(SELECT rn from t0
  5        where mod(rn,3)<>0
  6              and mod(rn,5)<>0
  7              and mod(rn,7)<>0
  8              and mod(rn,11)<>0
  9              and mod(rn,13)<>0
10              and mod(rn,17)<>0
11              and mod(rn,19)<>0
12              and mod(rn,23)<>0
13              and mod(rn,29)<>0
14      )
15  SELECT COUNT(*)+10 --2,3,5,7,11,13,17,19,23,29
16     FROM (SELECT rn from t
17           MINUS
18           SELECT /*+ USE_MERGE (t1 t2) */ t1.rn * t2.rn
19             FROM t t1, t t2
20           WHERE t1.rn <= t2.rn
21                 AND t1.rn BETWEEN 31 AND (SELECT SQRT(:n) FROM DUAL)
22                 AND t1.rn * t2.rn <:n and t2.rn<=:n/31
23         )
24  /

COUNT(*)+10--2,3,5,7,11,13,17,19,23,29
--------------------------------------
                                148933

已用时间:  00: 00: 03.71

〇〇

若不用use merge SQL> / COUNT(*)+10--2,3,5,7,11,13,17,19,23,29 --------------------------------------                                 148933 已用时间:  00: 00: 13.63 PLAN_TABLE_OUTPUT ------------------------------------------------------------------------------------------------------------------ Plan hash value: 1065182249 ---------------------------------------------------------------------------------------------------------------- | Id  | Operation                        | Name                        | Rows  | Bytes | Cost (%CPU)| Time     | ---------------------------------------------------------------------------------------------------------------- |   0 | SELECT STATEMENT                 |                             |     1 |       |    12  (17)| 00:00:01 | |   1 |  TEMP TABLE TRANSFORMATION       |                             |       |       |            |          | |   2 |   LOAD AS SELECT                 | SYS_TEMP_0FD9D6700_D0C33F9D |       |       |            |          | |*  3 |    VIEW                          |                             |     1 |    13 |     2   (0)| 00:00:01 | |   4 |     COUNT                        |                             |       |       |            |          | |*  5 |      CONNECT BY WITHOUT FILTERING|                             |       |       |            |          | |   6 |       FAST DUAL                  |                             |     1 |       |     2   (0)| 00:00:01 | |   7 |   SORT AGGREGATE                 |                             |     1 |       |            |          | |   8 |    VIEW                          |                             |     1 |       |    10  (20)| 00:00:01 | |   9 |     MINUS                        |                             |       |       |            |          | |  10 |      SORT UNIQUE                 |                             |     1 |    13 |     3  (34)| 00:00:01 | |  11 |       VIEW                       |                             |     1 |    13 |     2   (0)| 00:00:01 | |  12 |        TABLE ACCESS FULL         | SYS_TEMP_0FD9D6700_D0C33F9D |     1 |    13 |     2   (0)| 00:00:01 | |  13 |      SORT UNIQUE                 |                             |     1 |    26 |     7  (15)| 00:00:01 | |* 14 |       FILTER                     |                             |       |       |            |          | |  15 |        NESTED LOOPS              |                             |     1 |    26 |     4   (0)| 00:00:01 | |* 16 |         VIEW                     |                             |     1 |    13 |     2   (0)| 00:00:01 | |  17 |          TABLE ACCESS FULL       | SYS_TEMP_0FD9D6700_D0C33F9D |     1 |    13 |     2   (0)| 00:00:01 | |  18 |          FAST DUAL               |                             |     1 |       |     2   (0)| 00:00:01 | |* 19 |         VIEW                     |                             |     1 |    13 |     2   (0)| 00:00:01 | |  20 |          TABLE ACCESS FULL       | SYS_TEMP_0FD9D6700_D0C33F9D |     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 AND MOD("RN",23)<>0 AND MOD("RN",29)<>0)    5 - filter(ROWNUM<=TO_NUMBER(:N)/2-1-1)   14 - filter(TO_NUMBER(:N)/31>=31)   16 - filter("T1"."RN">=31 AND "T1"."RN"<= (SELECT SQRT(TO_NUMBER(:N)) FROM "SYS"."DUAL" "DUAL") AND               "T1"."RN"<=TO_NUMBER(:N)/31)   19 - filter("T1"."RN"<="T2"."RN" AND "T1"."RN"*"T2"."RN"<TO_NUMBER(:N) AND "T2"."RN">=31 AND               "T2"."RN"<=TO_NUMBER(:N)/31)

newkid

应该是因为CBO不能正确判断返回行数才错误地用了NESTED LOOPS. 这种<=的连接应该是SORT MERGE最快。