高效的sql素數算法

我意識到SQL並不是最好的語言，但這是一項家庭作業，要編寫一個函數，它將接受一個參數N，並且會找到1到10之間的素數（N = 10,000,000）百萬。我正在使用Postgresql。這裏是我的嘗試：高效的sql素數算法

--First create table Numbers with all numbers from 1 to 10000000 in it 

create table numbers(number bigint); 

--Use this function to fill it in: 

create or replace function populate(top bigint) RETURNS void as $$ 
declare 
i bigint:=1; 
begin 
while(i<=top) LOOP 
insert into numbers(number) 
values(i); 
i:=i+1; 
END LOOP; 
END; $$ LANGUAGE plpgsql; 

--Function primes that returns all primes up to N 

create or replace function primes(N bigint) RETURNS void AS $$ 

DECLARE 
first bigint :=3; 
last bigint :=2; 

BEGIN 
--create table t1 and insert all odd integers from 3 to N (and 2) 

create table t1(a bigint); 
INSERT into t1(a) 
select number 
from numbers 
where (number%2 <> 0 or number = 2) 
AND number<=N AND number<>1; 

--Use Sieve of Erastothenes to find primes 

while (last < sqrt(n)) LOOP 

first:= (select * from t1 where a>last order by a limit 1); 
last:= first* first; 

--delete from list of primes all multiples of the primes in the range of first-last 
-- (first run-through is primes in range of 3-9, second run-through would be primes in range of 11-121, etc.) 

delete from t1 
where a in (select n1.number * t.a 
from t1 as t 
inner join numbers as n1 
on n1.number >= t.a 
and n1.number<= n/t.a 
where t.a>=first 
and t.a<last); 

END LOOP; 
END; $$ LANGUAGE plpgsql;

來源

2013-02-25 user1657563

我看到你的嘗試。它出什麼問題了？ – 2013-02-25 20:35:50

在這裏看到我的問題：http://stackoverflow.com/q/14678734/905902（這是非常不同的，但可能是一個很好的閱讀）順便說一句：你不是唯一一個足夠愚蠢的人使用RDBMS計算素數... – wildplasser 2013-02-25 22:51:28

有人嚴重需要發佈二次篩的SQL實現。我最終可能會自己做，併發佈一個鏈接到代碼。 – devinbost 2015-10-15 00:16:21

的話題好好檢討是在這裏：http://sqlblog.com/blogs/hugo_kornelis/archive/2006/09/23/Prime-numbers.aspx

但對於一個家庭作業的問題，你應該做自己的工作。

來源

2013-02-25 20:01:49

我不認爲任何人會檢查或比較大部分這些貼子 - 我已經發布了一些可憐的跑步者來找出，但沒有人打電話給他們。如果你傾向於雖然比較，你會發現這種可讀性和快速：

IF (SELECT OBJECT_ID ('tempdb.dbo.#Numbers')) IS NOT NULL 
    DROP TABLE #Numbers; 
CREATE TABLE #Numbers (Prime INT NOT NULL, Squared BIGINT PRIMARY KEY CLUSTERED); 

DECLARE @MaxPrime INT = 1000000; 

;WITH 
GroupingDriver AS 
(
    SELECT CAST('7' AS BIGINT) as Interval 
    UNION ALL 
    SELECT Interval+30 
    FROM GroupingDriver 
    WHERE Interval+30 < @MaxPrime 
) 
INSERT INTO #Numbers 
SELECT 2 AS 'Number', 4 AS 'SquareNo' 
UNION ALL 
SELECT 3 AS 'Number', 9 AS 'SquareNo' 
UNION ALL 
SELECT 5 AS 'Number', 25 AS 'SquareNo' 
UNION ALL 
SELECT Prime.Number, Prime.Number * Prime.Number 
FROM GroupingDriver 
CROSS APPLY (VALUES (GroupingDriver.Interval), 
        (GroupingDriver.Interval+4), 
        (GroupingDriver.Interval+6), 
        (GroupingDriver.Interval+10), 
        (GroupingDriver.Interval+12), 
        (GroupingDriver.Interval+16), 
        (GroupingDriver.Interval+22), 
        (GroupingDriver.Interval+24)) AS Prime(Number) 
WHERE Prime.Number < @MaxPrime 
OPTION (MAXRECURSION 0);

現在，通過其他的素數刪除那些整除。我們只是使用平方作爲比較的截止點。

SELECT Prime 
FROM #Numbers n 
WHERE NOT EXISTS (SELECT 1 
        FROM #Numbers AS p 
        WHERE p.Squared <= n.Prime 
        AND n.Prime % p.Prime = 0); 
GO

來源

2015-09-28 11:01:00

高效的sql素數算法

回答

相關問題