用SQL计算100以内的质数
以前写过一篇文章，描述如何使用PL/SQL来计算100以内的质数，今天重翻那篇文章的时候，突然想到，能不能用SQL来实现同样的功能。
其实这个功能用PLSQL实现最简单，思路也很清晰，判断一个数是否是质数，只需要检查这个数能否被比它小的质数整除就可以了。但是这种操作通过SQL来实现就十分的困难，因此这里通过另外一种方式来实现这个功能——构造。
通过查询100以内的数，去掉所有的合数，剩下的就是质数了：
SQL> WITH T
2 AS
3 (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 100)
4 SELECT RN FROM T
5 WHERE RN > 1
6 MINUS
7 SELECT A.RN * B.RN FROM T A, T B
8 WHERE A.RN <= B.RN
9 AND A.RN > 1
10 AND B.RN > 1;
RN
----------
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
25 rows selected.
但是这种方法的效率明显要比PL/SQL的效率要低，如果取10000以内的质数：
SQL> SET TIMING ON
SQL> SET AUTOT TRACE STAT
SQL> WITH T
2 AS
3 (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 10000)
4 SELECT RN FROM T
5 WHERE RN > 1
6 MINUS
7 SELECT A.RN * B.RN FROM T A, T B
8 WHERE A.RN <= B.RN
9 AND A.RN > 1
10 AND B.RN > 1;
1229 rows selected.
Elapsed: 00:02:41.54
Statistics
----------------------------------------------------------
511 recursive calls
81 db block gets
180002 consistent gets
65131 physical reads
648 redo size
17139 bytes sent via SQL*Net to client
1276 bytes received via SQL*Net from client
83 SQL*Net roundtrips to/from client
2 sorts (memory)
1 sorts (disk)
1229 rows processed
这个SQL执行了2分半种以上，当然这个SQL还可以进行一下优化，比如A的取值可以小于10000的开方，而B的取值可以小于10000除以最小的质数：
SQL> WITH T
2 AS
3 (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 10000)
4 SELECT RN FROM T
5 WHERE RN > 1
6 MINUS
7 SELECT A.RN * B.RN FROM T A, T B
8 WHERE A.RN <= B.RN
9 AND A.RN > 1
10 AND A.RN <= 100
11 AND B.RN > 1
12 AND B.RN <= 5000;
1229 rows selected.
Elapsed: 00:00:00.78
Statistics
----------------------------------------------------------
2 recursive calls
23 db block gets
1820 consistent gets
16 physical reads
692 redo size
17139 bytes sent via SQL*Net to client
1276 bytes received via SQL*Net from client
83 SQL*Net roundtrips to/from client
3 sorts (memory)
0 sorts (disk)
1229 rows processed
优化后，SQL的执行效率提高了3个数量级，其实这个SQL仍然是可以优化的，考虑除了2以外，所有的质数均为奇数：
SQL> WITH T
2 AS
3 (SELECT ROWNUM * 2 + 1 RN FROM DUAL CONNECT BY LEVEL < 4999)
4 SELECT 2 FROM DUAL
5 UNION ALL
6 (
7 SELECT RN FROM T
8 WHERE RN > 1
9 MINUS
10 SELECT A.RN * B.RN FROM T A, T B
11 WHERE A.RN <= B.RN
12 AND A.RN > 1
13 AND A.RN <= 100
14 AND B.RN > 1
15 AND B.RN <= 5000
16 )
17 ;
1229 rows selected.
Elapsed: 00:00:00.25
Statistics
----------------------------------------------------------
2 recursive calls
15 db block gets
512 consistent gets
8 physical reads
648 redo size
17138 bytes sent via SQL*Net to client
1276 bytes received via SQL*Net from client
83 SQL*Net roundtrips to/from client
3 sorts (memory)
0 sorts (disk)
1229 rows processed
虽然通过SQL优化已经将极大的提高了效率，但是和PLSQL比，效率仍然相去甚远：
SQL> DECLARE
2 TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
3 V_RESULT T_RECORD;
4 I NUMBER DEFAULT 3;
5 N NUMBER DEFAULT 0;
6 BEGIN
7 --DBMS_OUTPUT.PUT_LINE(2);
8 V_RESULT(1) := 3;
9 WHILE(I < 10000) LOOP
10 FOR J IN 1..V_RESULT.COUNT LOOP
11 IF V_RESULT(J) * V_RESULT(J) > I THEN
12 --DBMS_OUTPUT.PUT_LINE(I);
13 V_RESULT(V_RESULT.COUNT + 1) := I;
14 EXIT;
15 END IF;
16 IF TRUNC(I/V_RESULT(J)) = I/V_RESULT(J) THEN
17 EXIT;
18 END IF;
19 END LOOP;
20 IF N = 2 THEN
21 I := I + 4;
22 N := 1;
23 ELSE
24 I := I + 2;
25 N := N + 1;
26 END IF;
27 END LOOP;
28 V_RESULT(0) := 2;
29 END;
30 /
PL/SQL procedure successfully completed.
Elapsed: 00:00:00.04
这说明使用SQL并不一定就是最佳选择，有的时候使用PLSQL效率反而会更高。使用合适的方法做适合的事情，一味追求使用单条SQL实现很可能会损失性能。
-The End-