1

我意识到 SQL 不是最好的语言，但这是一个家庭作业，要编写一个函数，该函数将接受参数 N 并找到 1 到 1000 万之间的素数 (N=10,000,000)。我正在使用 Postgresql。这是我的尝试：

--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;
4

2 回答 2

1

一个很好的主题回顾在这里：https ://sqlserverfast.com/blog/hugo/2006/09/the-prime-number-challenge-great-waste-of-time/

但是对于一个家庭作业问题，你应该做你自己的工作。

于 2013-02-25T20:01:49.637 回答
0

我认为没有人真正检查或比较这些帖子中的大多数 - 我发布了几个糟糕的跑步者只是为了找出答案，但没有人打电话给他们。如果你倾向于比较，你会发现这个可读且快速：

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-28T11:01:00.607 回答