用SQL计算100以内的质数

以前写过一篇文章，描述如何使用PL/SQL来计算100以内的质数，今天重翻那篇文章的时候，突然想到，能不能用SQL来实现同样的功能。

PLSQL计算质数：http://yangtingkun.itpub.net/post/468/53770

其实这个功能用PLSQL实现最简单，思路也很清晰，判断一个数是否是质数，只需要检查这个数能否被比它小的质数整除就可以了。

但是这种操作通过SQL来实现就十分的困难。

因此这里通过另外一种方式来实现这个功能——构造。

通过查询100以内的数，去掉所有的合数，剩下的就是质数了：

SQL> WITH T
8~L)d;}~1v0  2  ASITPUB个人空间|b4I6M!vK
v+W
  3  (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 100)ITPUB个人空间g8J| ARhe
  4  SELECT RN FROM TITPUB个人空间 bn&_-^!pr2f3b3~;{1r yL
  5  WHERE RN > 1ITPUB个人空间mmhLEW
  6  MINUSITPUB个人空间"dH `HyV_
  7  SELECT A.RN * B.RN FROM T A, T B
8D/e7y6c:GL$[;u0  8  WHERE A.RN <= B.RN
\gG,} E7V0  9  AND A.RN > 1
m8|}MIDH0 10  AND B.RN > 1;

        RNITPUB个人空间1p3S"q/v2R
----------
JH+Y.\vn$L0         2
8~ m
D8v#c}x0         3
h1KuJ2}X0         5ITPUB个人空间H+z4~l-oT1P@/X!L
         7
;z,Ce(OT?0FNo"y0        11
OVc6{vntu2r)[0        13ITPUB个人空间D0nB kQ)[)n
        17
5g}#zw#w%L5@I;X0        19
W
bc)b~/L0        23ITPUB个人空间'G/]'T,sR{|
        29

r7V6LM(?VB.FaQ0        31
,iD1h6^p*kM!L,o0        37ITPUB个人空间BE1@/Q.G"g&h:wV
        41
)Zw*t{O,i)gA0        43ITPUB个人空间v9yFK9G1[
_ bLC\
        47ITPUB个人空间)f)lGToG c&W
Y
        53ITPUB个人空间 DEXy5SV
        59ITPUB个人空间]rnKA
        61ITPUB个人空间p2Q$Om^q
        67ITPUB个人空间 \UcL'Q'SdZ
        71ITPUB个人空间:^:^1_)x {J+HF
        73
t8Ag^"h(KN\0        79ITPUB个人空间'e7YW'eI
        83
TPNl-vrfL0        89ITPUB个人空间(FZ7Kg H0z-z#{
        97

已选择25行。

但是这种方法的效率明显要比PL/SQL的效率要低，如果取10000以内的质数：

SQL> SET AUTOT TRACE STATITPUB个人空间
j5`"u6HC]rK
SQL> WITH T
0V2@-gn'p0  2  AS
/cAsM0_2j[E T0  3  (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 10000)
-g:bX'NTUn0  4  SELECT RN FROM T
FT*F~
C[n7d$J0  5  WHERE RN > 1ITPUB个人空间0z'y3Xy%Vg{A
  6  MINUS
H:x h$JZ-og;d0  7  SELECT A.RN * B.RN FROM T A, T BITPUB个人空间 r%It(VD(e-K+[9^c
  8  WHERE A.RN <= B.RN
q Zwo3B,c0  9  AND A.RN > 1
'cD_4zGz)X9h0 10  AND B.RN > 1;

已选择1229行。

已用时间:  00: 02: 41.54

统计信息
a%N
D4kFG5} Kh'qn0----------------------------------------------------------ITPUB个人空间RsdY?y.G/D5B`
        511  recursive callsITPUB个人空间A&Q8t4opIi]P
         81  db block getsITPUB个人空间Z;sk2\L
     180002  consistent getsITPUB个人空间\
t#ytw5ev0b1GD
      65131  physical readsITPUB个人空间+tt qO2N'}B_
        648  redo size
0p,~:eLMV!k,qAl0      17139  bytes sent via SQL*Net to clientITPUB个人空间q-Bm#t2x
tg
       1276  bytes received via SQL*Net from clientITPUB个人空间ShA4gVZ
         83  SQL*Net roundtrips to/from client
8kf"`v)Z#?;X(^7M]0          2  sorts (memory)ITPUB个人空间ak qI8@mh3qEM
          1  sorts (disk)
+l8H:V,H#Wo0       1229  rows processed

这个SQL执行了2分半种以上，当然这个SQL还可以进行一下优化，比如A的取值可以小于10000的开方，而B的取值可以小于10000除以最小的质数：

SQL> WITH T
9Su_B2M7tG0  2  AS
j*Cv%Ers[0  3  (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 10000)ITPUB个人空间6? BR:Sc
`g
  4  SELECT RN FROM T
|[+pQ#jJBP#?0  5  WHERE RN > 1ITPUB个人空间t.Lj2b{-i#S#o)@%@V
  6  MINUSITPUB个人空间r$J&~o:W"pRT:qH
  7  SELECT A.RN * B.RN FROM T A, T B
l~.r{(D*g0  8  WHERE A.RN <= B.RN

N({*l(k#Z1H#S_0  9  AND A.RN > 1ITPUB个人空间E~Ea!c e-I
 10  AND A.RN <= 100ITPUB个人空间#qSFZa*w.p'Wk#c
 11  AND B.RN > 1
*O.thb0|b$?0 12  AND B.RN <= 5000;

已选择1229行。

已用时间:  00: 00: 00.78

统计信息ITPUB个人空间 y A I*{2v1b
----------------------------------------------------------ITPUB个人空间A(L:T'F&LaL6a
          2  recursive calls
6T8Mb1Ay~ _!C0         23  db block gets

LB:Hs+kDD(L0       1820  consistent gets
z%X/dh;zU6[0         16  physical readsITPUB个人空间0O AEK0m }2Sg]?
        692  redo size
7R\I6Pwz0      17139  bytes sent via SQL*Net to client
i+r!L;{n-ae1v f0       1276  bytes received via SQL*Net from clientITPUB个人空间-j+_^ H$cSX T
         83  SQL*Net roundtrips to/from clientITPUB个人空间}9[UM3nj$FH+F
          3  sorts (memory)ITPUB个人空间3x\N$J8I ?
          0  sorts (disk)ITPUB个人空间FG;U)v9jyK
       1229  rows processed

优化后，SQL的执行效率提高了3个数量级，其实这个SQL仍然是可以优化的，考虑除了2以外，所有的质数均为奇数：

SQL> WITH TITPUB个人空间n1r7@oo ZW
  2  AS
s:u5A&WoI
HH!U;Q0  3  (SELECT ROWNUM * 2 + 1 RN FROM DUAL CONNECT BY LEVEL < 4999)
O;z~a'@0  4  SELECT 2 FROM DUALITPUB个人空间N}0saz_;b7c\S1L
  5  UNION ALL
4ak-Xig[C0  6  (
J qjFt0q[*b0  7   SELECT RN FROM TITPUB个人空间1f2j9|jt'H&]9eeZo
  8   WHERE RN > 1
.\?E(}B*a0  9   MINUS
7M Z"n&n2~B z}0 10   SELECT A.RN * B.RN FROM T A, T BITPUB个人空间)O V
Y$?A,O/p_t0|
 11   WHERE A.RN <= B.RNITPUB个人空间G
O)?t i7e0DY
 12   AND A.RN > 1ITPUB个人空间\(c_ve`6lx&~
 13   AND A.RN <= 100ITPUB个人空间Lj,i'|q3Lh j
 14   AND B.RN > 1ITPUB个人空间 O@&A @%S/|w
 15   AND B.RN <= 5000
pbr9u5e_/]7B0 16  )
Fv/c H W*`$Q~2F;|0 17  ;

已选择1229行。

已用时间:  00: 00: 00.25

统计信息ITPUB个人空间5]x9H
tI9R%^V
----------------------------------------------------------ITPUB个人空间~a/@xv)AA6v'U
          2  recursive callsITPUB个人空间`5BsAF
@sO
         15  db block getsITPUB个人空间`My7~,P
        512  consistent getsITPUB个人空间A&{kDG%Y'|n$R2N
          8  physical readsITPUB个人空间QJl^-N7~Ok1u
        648  redo size
9X @+zog$Z` j(AG0      17138  bytes sent via SQL*Net to client
Jh?qt!}/u0       1276  bytes received via SQL*Net from clientITPUB个人空间q`;po\fez
         83  SQL*Net roundtrips to/from client
V {1ffbU9q%D7F0          3  sorts (memory)ITPUB个人空间_XpUL-Jv;Y8SQ
          0  sorts (disk)
ro H1Q{f&H[0       1229  rows processed

虽然通过SQL优化已经将极大的提高了效率，但是和PLSQL比，效率仍然相去甚远：

SQL> DECLARE
e `L$~;}l0  2   TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;ITPUB个人空间'\;]}(mb,I-v
  3   V_RESULT T_RECORD;ITPUB个人空间Y,U'T&~$V'C6? s
  4   I NUMBER DEFAULT 3;
:u2D/u_ Z0  5   N NUMBER DEFAULT 0;
0t'DO"U,w$f*Lbx0  6  BEGIN
6z
l0Gb:G0  7   --DBMS_OUTPUT.PUT_LINE(2);
l s(iB_RPO8S0  8   V_RESULT(1) := 3;ITPUB个人空间.ncWr)S)i
  9   WHILE(I < 10000) LOOPITPUB个人空间zw/nO](a t x
 10    FOR J IN 1..V_RESULT.COUNT LOOP
Dj1R:O7msZ0 11     IF V_RESULT(J) * V_RESULT(J) > I THEN
DPZy~m*x
oF+k;u(\0 12      --DBMS_OUTPUT.PUT_LINE(I);
@E4{&A"q0 13      V_RESULT(V_RESULT.COUNT + 1) := I;ITPUB个人空间"C4O;V/d'h"[+_
 14      EXIT;ITPUB个人空间g!H?@.C*]
 15     END IF;ITPUB个人空间yPu iF\2F
 16     IF TRUNC(I/V_RESULT(J)) = I/V_RESULT(J) THENITPUB个人空间-V9T]4F2N5i^
 17      EXIT;ITPUB个人空间u.G_%bK6~_/iwQ
 18     END IF;
E!@7RQ9jG |0 19    END LOOP;
I T"N6}5Y!g$V2fj8QW0 20    IF N = 2 THENITPUB个人空间7q4^L9}+mX
 21     I := I + 4;ITPUB个人空间\,{Tq-b+Y
 22     N := 1;ITPUB个人空间t:n:L?-p#C8B
 23    ELSEITPUB个人空间B#rrHr)P-k N
 24     I := I + 2;
7FS#J,ub'sP:M'e5m0 25     N := N + 1;
ppzG \"GR0 26    END IF;ITPUB个人空间X8[)z)k3tkG
 27   END LOOP;ITPUB个人空间C*WWK(EbQE)D
 28   V_RESULT(0) := 2;ITPUB个人空间jn cH5v*s0h,sj
}DP
 29  END;
hJZw n,_$?7Tct0 30  /

PL/SQL过程已成功完成。

已用时间:  00: 00: 00.04ITPUB个人空间^4|(aql3n2A
SQL>

这说明使用SQL并不一定就是最佳选择，有的时候使用PLSQL效率反而会更高。使用合适的方法做适合的事情，一味追求使用单条SQL实现很可能会损失性能。