sql求解200万内质数各种算法点评

winxos

如果只是求个数，目前最快的算法是根据sqrt（n）以内的素数就可以推算出n以内的个数。

newkid

winxos 发表于 2014-3-21 20:20
如果只是求个数，目前最快的算法是根据sqrt（n）以内的素数就可以推算出n以内的个数。

思路挺不错，但是具体怎么推算？还得对所有素数因子的组合做乘法吧？

lastwinner

winxos 发表于 2014-3-21 20:20
如果只是求个数，目前最快的算法是根据sqrt（n）以内的素数就可以推算出n以内的个数。

能么？
如果能，也是个大概数吧

dcllj

分析的有理有据。

luoyoumou

-- 贴个用“存储过程”的写法：

CREATE TYPE prime_ot AS OBJECT
(  prime_num NUMBER(38,0)
)
/

-- 创建这个对象的集合，用于定义函数的返回值类型
CREATE TYPE prime_nnt AS TABLE OF prime_ot
/

-- 创建临时表，用以存放素数
CREATE GLOBAL TEMPORARY TABLE tmp_prime(
  prime_num NUMBER(38,0)
)
ON COMMIT DELETE ROWS;


CREATE OR REPLACE PROCEDURE pro_prime(i_end_num in number, o_cur OUT SYS_REFCURSOR)
IS
  CURSOR l_prime_cur(c_end_num in number)
  IS
    SELECT 3+(level-1)*2 as prime_num
    FROM dual
    CONNECT BY level<(c_end_num/2);

  TYPE l_prime_aat IS TABLE OF l_prime_cur%ROWTYPE
    INDEX BY BINARY_INTEGER;
  l_prime_curs l_prime_aat;
  l_prime_ot prime_ot := prime_ot(NULL);

  TYPE l_prime_aat2 IS TABLE OF l_prime_cur%ROWTYPE
    INDEX BY BINARY_INTEGER;
  l_prime_curs2 l_prime_aat2;
  l_prime_ot2 prime_ot := prime_ot(NULL);

  CURSOR l_prime_print
  IS
    SELECT prime_num
    FROM dbmon.tmp_prime
    ORDER BY prime_num;

  l_is_prime NUMBER(10,0);
  v_prime_num NUMBER(38,0);

BEGIN
  TRUNCATE TABLE dbmon.tmp_prime;
  IF i_end_num>=3 THEN
    OPEN l_prime_cur(i_end_num);
    LOOP
      FETCH l_prime_cur BULK COLLECT INTO l_prime_curs LIMIT 2000;
        FOR l_row IN 1..l_prime_curs.COUNT
        LOOP
          v_prime_num := l_prime_curs(l_row).prime_num;
          SELECT COUNT(1) INTO l_is_prime
          FROM tmp_prime t1
          WHERE t1.prime_num<=SQRT(v_prime_num)+1
            AND mod(v_prime_num,t1.prime_num)=0;

          IF l_is_prime=0 THEN
            INSERT INTO dbmon.tmp_prime(prime_num) VALUES(v_prime_num);
          END IF;
        END LOOP;
      EXIT WHEN l_prime_cur%NOTFOUND;
    END LOOP;
    CLOSE l_prime_cur;
    INSERT INTO  tmp_prime(prime_num) VALUES(2);
  END IF;

  OPEN o_cur FOR 'SELECT prime_num FROM dbmon.tmp_prime order by prime_num';
EXCEPTION WHEN OTHERS THEN
  CLOSE l_prime_cur;
END;
/

-------------

set serveroutput on;
var c_cur refcursor;
exec dbmon.pro_prime(20000,:c_cur);
print c_cur;

lastwinner

luoyoumou 发表于 2014-3-25 19:35
-- 贴个用“存储过程”的写法：

CREATE TYPE prime_ot AS OBJECT

嗯，递归做起来容易很多了
你测过效率对比没？

luoyoumou

lastwinner 发表于 2014-3-26 00:45
嗯，递归做起来容易很多了
你测过效率对比没？

效率当然是你的高，扛扛的。

luoyoumou

lastwinner 发表于 2014-3-26 00:45
嗯，递归做起来容易很多了
你测过效率对比没？

效率当然是你的高，扛扛的。

luoyoumou

lastwinner 发表于 2014-3-26 00:45
嗯，递归做起来容易很多了
你测过效率对比没？

效率当然是你的高，扛扛的。

lastwinner

luoyoumou 发表于 2014-3-28 19:47
效率当然是你的高，扛扛的。

要这样说，那pl/sql里你采取小批量处理的策略，而不是一个一个去处理，会快更多