求200万以内质数的个数

〇〇

学习

〇〇

去掉order by，加rule 提示
SQL> with t as(select level*2+1 l from dual connect by level<=1E4),
  2  t1 as(select l from t where l<=sqrt(2)*1E2 and l>=11)
  3  select count(t.l) from (select l from t where mod(l,3)<>0 and mod(l,5)<>0 and mod(l,7)<>0)t
  4  where not exists(select t1.l from t1
  5  where t1.l<=sqrt(t.l) and mod(t.l,t1.l)=0)
  6  /

COUNT(T.L)
----------
      2258

Elapsed: 00:00:36.11
SQL> with t as(select level*2+1 l from dual connect by level<=1E4),
  2  t1 as(select l from t where l<=sqrt(2)*1E2 and l>=11)
  3  select count(t.l) from (select /*+rule*/ l from t where mod(l,3)<>0 and mod(l,5)<>0 and mod(l,7)<>0)t
  4  where not exists(select t1.l from t1
  5  where t1.l<=sqrt(t.l) and mod(t.l,t1.l)=0)
  6  /

COUNT(T.L)
----------
      2258

Elapsed: 00:00:05.11

不过我的试除取余法本来就比不上筛法

〇〇

8楼有个小问题，t中有偶数，直接用t_odd更快


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

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

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

Elapsed: 00:00:00.53

〇〇

排除几个明显的还是更快
SQL> WITH t0 AS (
  2     SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 10000-1
  3     ),
  4  t as(SELECT rn from t0 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0)
  5  SELECT COUNT(*)+1+3 --2，3，5，7
  6    FROM (SELECT rn from t
  7          MINUS
  8          SELECT t1.rn * t2.rn
  9            FROM t t1, t t2
10           WHERE t1.rn <= t2.rn
11                 AND t1.rn <= (SELECT SQRT(20000) FROM DUAL)
12                 AND t1.rn * t2.rn <20000
13         )
14  /

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

Elapsed: 00:00:00.18

〇〇

ibm 570 aix 11g:
SQL> WITH t0 AS (
  2     SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 1000000-1
  3     ),
  4  t as(SELECT rn from t0 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0)
  5  SELECT COUNT(*)+1+3
  6    FROM (SELECT rn from t
  7          MINUS
  8          SELECT t1.rn * t2.rn
  9            FROM t t1, t t2
10           WHERE t1.rn <= t2.rn
11                 AND t1.rn <= SQRT(2000000)
12                 AND t1.rn * t2.rn <2000000
13         )
14  /

COUNT(*)+1+3
------------
      148933

已用时间:  00: 01: 05.61
windows
10g xe
SQL> WITH t0 AS (
  2     SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 1000000-1
  3     ),
  4  t as(SELECT rn from t0 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0)
  5  SELECT COUNT(*)+1+3
  6    FROM (SELECT rn from t
  7          MINUS
  8          SELECT t1.rn * t2.rn
  9            FROM t t1, t t2
10           WHERE t1.rn <= t2.rn
11                 AND t1.rn <= SQRT(2000000)
12                 AND t1.rn * t2.rn <2000000
13         )
14  /

COUNT(*)+1+3
------------
      148933

Elapsed: 00:01:19.75

newkid

你这一改确实管用，现在200万也只需要半分钟了：

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)
SELECT COUNT(*)+1+3 --2，3，5，7
   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 9 AND (SELECT SQRT(:n) FROM DUAL)
               AND t1.rn * t2.rn <:n
       )
/


COUNT(*)+1+3
-----------------------
                 148933

Elapsed: 00:00:29.63

〇〇

你的计算机速度比power 570还快！

zhangweicai74

学习.

〇〇

xe
SQL> var n number;
SQL> exec :n:=2000000;

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.81
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 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0)
  5  SELECT COUNT(*)+1+3 --2，3，5，7
  6     FROM (SELECT rn from t
  7           MINUS
  8           SELECT t1.rn * t2.rn
  9             FROM t t1, t t2
10           WHERE t1.rn <= t2.rn
11                 AND t1.rn BETWEEN 9 AND (SELECT SQRT(:n) FROM DUAL)
12                 AND t1.rn * t2.rn <:n
13         )
14  /

COUNT(*)+1+3--2，3，5，7
------------------------
                  148933

Elapsed: 00:01:06.32
SQL> 11
11*                AND t1.rn BETWEEN 9 AND (SELECT SQRT(:n) FROM DUAL)
SQL> c/BETWEEN 9 AND/<=
11*                AND t1.rn <= (SELECT SQRT(:n) FROM DUAL)
SQL> /

COUNT(*)+1+3--2，3，5，7
------------------------
                  148933

Elapsed: 00:00:49.07
SQL> 11
11*                AND t1.rn <= (SELECT SQRT(:n) FROM DUAL)
SQL> c/(SELECT SQRT(:n) FROM DUAL)/SQRT(:n)
11*                AND t1.rn <= SQRT(:n)
SQL> /

COUNT(*)+1+3--2，3，5，7
------------------------
                  148933

Elapsed: 00:00:40.39

〇〇

9i
14  /
    SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/2-1-1
                                       *
ERROR 位于第 2 行:
ORA-01652: 无法通过2048（在表空间LTTEMPTS中）扩展 temp 段


已用时间:  00: 00: 54.03
SQL> conn sys/sys as sysdba
已连接。
SQL> var n number;
SQL> exec :n:=2000000;

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
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 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0)
  5  SELECT COUNT(*)+1+3 --2，3，5，7
  6     FROM (SELECT rn from t
  7           MINUS
  8           SELECT t1.rn * t2.rn
  9             FROM t t1, t t2
10           WHERE t1.rn <= t2.rn
11                 AND t1.rn <= SQRT(:n)
12                 AND t1.rn * t2.rn <:n
13         )
14  /
    SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/2-1-1
                              *
ERROR 位于第 2 行:
ORA-00028: 您的会话己被删去


已用时间:  00: 13: 47.01