用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-