create function dbo.F_TABLE_PRIME(@MaxNumber bigint)
returns @t table (i bigint primary key) as
begin
insert @t select NUMBER from dbo.F_TABLE_NUMBER_RANGE(2, @MaxNumber)
declare @i bigint
set @i = 1
while 1 = 1
begin
select @i = min(i) from @t where i > @i
if @i is null or @i * @i > @MaxNumber break
delete @t where i > @i and i % @i = 0
end
return
end
go
select * from dbo.F_TABLE_PRIME(100000) order by i

Basically, you only need to check up to the square root of the candidate prime, because if a number has a factor, at least one will be less than or equal to the square root.

Basically, you only need to check up to the square root of the candidate prime, because if a number has a factor, at least one will be less than or equal to the square root.

CODO ERGO SUM

Yeah, I tried that before I posted, using this instead of the delete I have:

delete @t where i >= (@i * @i) and i % @i = 0

It didn't seem to make any difference (and I can see why), so I left it off. Can you see a better way to implement that idea?

Without any functions you can do this - I'm sure that given enough years it will give all the primes up to 1,024,031. Didn't bother to try and optimise it as was just trying to use a CTE.

with n (i, j) as ( select i = 0, j = 0 union all select i = i + 1, j = j + 1 from n where i < 32000 ) select na.i from (select i = j + k from n, (select k = j * 32001 from n where j < 32) n2) na left join (select distinct x = n1.i * n2.i from (select i = j + k from n, (select k = j * 32001 from n where j < 32) n2 where j+k >= 2) n1, (select i = j + k from n, (select k = j * 32001 from n where j < 32) n2 where j+k >= 2) n2 ) t on t.x = na.i where t.x is null option (MAXRECURSION 32767)

works well up to 120 with n (i, j) as ( select i = 0, j = 0 union all select i = i + 1, j = j + 1 from n where i < 10 ) select na.i from (select i = j + k from n, (select k = j * 11 from n where j < 32) n2) na left join (select distinct x = n1.i * n2.i from (select i = j + k from n, (select k = j * 11 from n where j < 32) n2 where j+k >= 2) n1, (select i = j + k from n, (select k = j * 11 from n where j < 32) n2 where j+k >= 2) n2 ) t on t.x = na.i where t.x is null option (MAXRECURSION 32767)

========================================== Cursors are useful if you don't know sql. DTS can be used in a similar way. Beer is not cold and it isn't fizzy.

I had a script for primes that I worked on for awhile, and then set it aside because I was hoping to find a better approach. It implements the Sieve of Eratosthenes, along with some ideas I stole from the Sieve of Atkin.

I ran the following tests to compare the speed to your function. I ran these on my home computer. I ran each 4 times, and I posted the best result for each below.

First I used this to run your function:

declare @T_PRIME table (PRIME int primary key clustered )
declare @start datetime
select @start = getdate()
insert into @T_PRIME
select i
from dbo.F_TABLE_PRIME(1000000) order by i
select [Elapsed time]=right(convert(varchar(24),getdate()-@start,121),12)
select
[Prime Count] = count(*),
[Last Prime] = max(PRIME)
from @T_PRIME

Results:

(78498 row(s) affected)
Elapsed time
------------
00:00:47.267
(1 row(s) affected)
Prime Count Last Prime
----------- -----------
78498 999983
(1 row(s) affected)

Then I ran my script for the same number of primes.

set nocount on
declare @num int
declare @limit int
declare @cnt int
declare @sqrt int
declare @rm60 int
declare @start datetime
declare @T_PRIME table (PRIME int primary key clustered )
insert into @T_PRIME (prime) select 2
set @num = 1
set @limit = 1000000
--set @limit = 16000000
set @cnt = 0
select @start = getdate()
while @num < @limit
begin
set @num = @num+2
-- Partial implementation Sieve of Atkin
if @num > 199
if
(@num%2=0) or (@num%3=0) or (@num%5=0) or (@num%7=0) or
(@num%11=0) or (@num%13=0) or (@num%17=0) or (@num%19=0) or
(@num%23=0) or (@num%29=0) or (@num%31=0) or (@num%37=0) or
(@num%41=0) or (@num%43=0) or (@num%47=0) or (@num%53=0) or
(@num%59=0) or (@num%61=0) or (@num%67=0) or (@num%71=0) or
(@num%73=0) or (@num%79=0) or (@num%83=0) or (@num%89=0) or
(@num%97=0) or (@num%101=0) or (@num%103=0) or (@num%107=0) or
(@num%109=0) or (@num%113=0) or (@num%127=0) or (@num%131=0) or
(@num%137=0) or (@num%139=0) or (@num%149=0) or (@num%151=0) or
(@num%157=0) or (@num%163=0) or (@num%167=0) or (@num%173=0) or
(@num%179=0) or (@num%181=0) or (@num%191=0) or (@num%193=0) or
(@num%197=0) or (@num%199=0)
continue
set @sqrt = floor(sqrt(@num))
insert into @T_PRIME (prime)
select @num
where
not exists (
select
*
from @T_PRIME a
where
PRIME <= @sqrt and
@num%a.PRIME = 0
)
set @cnt = @cnt+1
end -- end while
select [Elapsed time]=right(convert(varchar(24),getdate()-@start,121),12)
select [Limit] = @limit,
[table scan count] = @cnt,
[Prime Count] = count(*),
[Last Prime] = max(PRIME)
from @T_PRIME
select [Last Prime] =max(PRIME)
from (select top 1000000 * from @T_PRIME order by PRIME ) A

Results:

Elapsed time
------------
00:00:30.953
Limit table scan count Prime Count Last Prime
----------- ---------------- ----------- -----------
1000000 102851 78498 999983
Last Prime
-----------
999983

Next I tried checking the first 5,000,000 numbers. I ran each once; I didn't have the patience for more.

Results for my script:

Elapsed time
------------
00:02:58.057
Limit table scan count Prime Count Last Prime
----------- ---------------- ----------- -----------
5000000 521833 348513 4999999
Last Prime
-----------
4999999

Results for your function:

(348513 row(s) affected)
Elapsed time
------------
00:08:50.043
(1 row(s) affected)
Prime Count Last Prime
----------- -----------
348513 4999999
(1 row(s) affected)

CODO ERGO SUM

Edited by - Michael Valentine Jones on 07/26/2006 23:23:57

create function dbo.F_TABLE_PRIME(@MaxNumber bigint)
returns @t table (i bigint primary key) as
begin
declare @SqrtMaxNumber bigint
set @SqrtMaxNumber = sqrt(@MaxNumber)
declare @u table (i bigint primary key, j bigint)
insert @u select NUMBER, NUMBER * NUMBER from dbo.F_TABLE_NUMBER_RANGE(1, @SqrtMaxNumber)
--put in candidate primes
-- (integers which have an odd number of representations by certain quadratic forms)
insert @t
select 2 union all select 3 union all
select k from (
select k from (select 4 * a.j + b.j as k from @u a, @u b) c where k <= @MaxNumber and k % 12 in (1, 5)
union all
select k from (select 3 * a.j + b.j as k from @u a, @u b) c where k <= @MaxNumber and k % 12 = 7
union all
select k from (select 3 * a.j - b.j as k from @u a inner join @u b on a.i > b.i) c where k <= @MaxNumber and k % 12 = 11
) d group by k having count(*) in (1, 3)
--eliminate composites by sieving
declare @i bigint
set @i = 5
while @i * @i < @MaxNumber
begin
delete @t where i > @i and i % @i = 0
select @i = min(i) from @t where i > @i
end
return
end
go

The results (for me, on my machine) are as follows (all in seconds)...

A: Ryan's 1st effort (Sieve of Eratosthenes) B: Michael's improvement (Sieve of Eratosthenes/Aitken) C: Ryan's 2nd effort (Sieve of Aitken)

Number of Records A B C
----------------- ------ ----- -----
100000 1.6 1.3 .6
1000000 21.0 14.0 7.0
5000000 134.0 80.0 55.0

I've changed the while loop in favour of recursion, and (in this case) that will give fewer loops.

I've also changed it so it works for @MaxNumber < 3.

In my tests, it performed about 10% quicker than the previous version (C).

create function dbo.F_TABLE_PRIME(@MaxNumber bigint)
returns @t table (i bigint primary key) as
begin
declare @SqrtMaxNumber bigint
set @SqrtMaxNumber = sqrt(@MaxNumber)
declare @u table (i bigint primary key, j bigint)
insert @u select NUMBER, NUMBER * NUMBER from dbo.F_TABLE_NUMBER_RANGE(1, @SqrtMaxNumber)
--put in candidate primes
-- (integers which have an odd number of representations by certain quadratic forms)
insert @t
select 2 union all select 3 union all
select k from (
select k from (select 4 * a.j + b.j as k from @u a, @u b) c where k <= @MaxNumber and k % 12 in (1, 5)
union all
select k from (select 3 * a.j + b.j as k from @u a, @u b) c where k <= @MaxNumber and k % 12 = 7
union all
select k from (select 3 * a.j - b.j as k from @u a inner join @u b on a.i > b.i) c where k <= @MaxNumber and k % 12 = 11
) d group by k having count(*) in (1, 3)
--eliminate composites by sieving
if @MaxNumber > 5
delete a from @t a, dbo.F_TABLE_PRIME(@SqrtMaxNumber) b where a.i >= b.i * b.i and a.i % b.i = 0
else
delete from @t where i > @MaxNumber --so works for i < 3
return
end
go

I wonder how much of the runtime of the F_TABLE_PRIME function is due to the overhead of running the F_TABLE_NUMBER_RANGE function? Have you looked at that?

quote:Originally posted by Michael Valentine Jones

I wonder how much of the runtime of the F_TABLE_PRIME function is due to the overhead of running the F_TABLE_NUMBER_RANGE function? Have you looked at that?

CODO ERGO SUM

Yeah, it's pretty insignificant because we're only using F_TABLE_NUMBER_RANGE to generate numbers to @SqrtMaxNumber (so for @MaxNumber = 1,000,000 it only generates numbers 1-1,000), and as you know F_TABLE_NUMBER_RANGE is like lightning for that kind of range.

a) select 2 union all select 3 union all
b) having count(k) in (1, 3)
c) set @i = 5
d) select * from @t

to

a) select 2 union all select 3 union all select 5 union all
b) having count(k) in (1, 3) and k % 10 in (1,3,7,9)
c) set @i = 7
d) select * from @t where i <= @maxnumber

quote:Originally posted by Michael Valentine Jones

I wonder how much of the runtime of the F_TABLE_PRIME function is due to the overhead of running the F_TABLE_NUMBER_RANGE function? Have you looked at that?

CODO ERGO SUM

Yeah, it's pretty insignificant because we're only using F_TABLE_NUMBER_RANGE to generate numbers to @SqrtMaxNumber (so for @MaxNumber = 1,000,000 it only generates numbers 1-1,000), and as you know F_TABLE_NUMBER_RANGE is like lightning for that kind of range.

a) select 2 union all select 3 union all
b) having count(k) in (1, 3)
c) set @i = 5
d) select * from @t

to

a) select 2 union all select 3 union all select 5 union all
b) having count(k) in (1, 3) and k % 10 in (1,3,7,9)
c) set @i = 7
d) select * from @t where i <= @maxnumber

I have come across an algorithm which can tell you what odd positive integer that is NOT a prime. I am verifying my results right now. As of now, all primes up to 10,007 have been verified. I will post my result here soon. I have a two-and-a-half-year daughter to attend to too

/* DROP TABLE dbo.TallyPrime
CREATE TABLE dbo.TallyPrime
(
Number BIGINT PRIMARY KEY CLUSTERED,
a BIGINT NOT NULL,
b BIGINT NOT NULL,
p1 BIGINT NOT NULL,
p2 BIGINT NOT NULL,
n1 BIGINT NOT NULL,
n2 BIGINT NOT NULL,
y1 BIGINT NOT NULL,
y2 BIGINT NOT NULL
)
INSERT dbo.TallyPrime
(
Number,
a,
b,
p1,
p2,
n1,
n2,
y1,
y2
)
SELECT Number,
2 * Number * Number + 2 * Number AS a,
2 * Number + 1 AS b,
(SQRT(6 * Number - 1) - 1) / 2 AS p1,
(SQRT(6 * Number + 1) - 1) / 2 AS p2,
6 * Number - 1 AS n1,
6 * Number + 1 AS n2,
3 * Number - 1 AS y1,
3 * Number AS y2
FROM (
SELECT TOP(2000000)
CAST(2048 * v1.Number + v2.Number AS BIGINT) AS Number
FROM master..spt_values AS v1
INNER JOIN master..spt_values AS v2 ON v2.Type = 'P'
WHERE v1.Type = 'P'
AND 2048 * v1.Number + v2.Number >= 1
ORDER BY 2048 * v1.Number + v2.Number
) AS d
ORDER BY Number
*/
DECLARE @MaxPrime INT
SET @MaxPrime = 10000
SELECT 2 AS Prime UNION ALL
SELECT 3 UNION ALL
SELECT d.Number
FROM (
SELECT n1 AS Number,
y1 AS Yak,
p1 AS Peso
FROM TallyPrime
WHERE Number <= FLOOR((@MaxPrime + 1) / 6.0)
UNION ALL
SELECT n2 AS Number,
y2 AS Yak,
p2 AS Peso
FROM TallyPrime
WHERE Number <= FLOOR((@MaxPrime - 1) / 6.0)
) AS d
WHERE NOT EXISTS (
SELECT *
FROM TallyPrime AS e
WHERE e.Number <= d.Peso
AND (d.Yak - e.a) % e.b = 0
)

--SieveOfBlindman
--7/28/2009
--------------------------------------------------------------------------------
--This script returns all the prime numbers between 0 and 1000.
--It is based on a new algorithm which leverages the fact that all these prime
--numbers have already been calculated God-knows how many bazillion times, so
--why bother calculating them again?
--I believe this is the fastest know algorithm for returning prime numbers
--less than 1000. The algorithm could easily be extended to larger prime
--numbers as well, but I will leave it to others to work out the details.
--------------------------------------------------------------------------------
select 2 union select 3 union select 5 union select 7 union select 11
union select 13 union select 17 union select 19 union select 23 union select 29
union select 31 union select 37 union select 41 union select 43 union select 47
union select 53 union select 59 union select 61 union select 67 union select 71
union select 73 union select 79 union select 83 union select 89 union select 97
union select 101 union select 103 union select 107 union select 109 union select 113
union select 127 union select 131 union select 137 union select 139 union select 149
union select 151 union select 157 union select 163 union select 167 union select 173
union select 179 union select 181 union select 191 union select 193 union select 197
union select 199 union select 211 union select 223 union select 227 union select 229
union select 233 union select 239 union select 241 union select 251 union select 257
union select 263 union select 269 union select 271 union select 277 union select 281
union select 283 union select 293 union select 307 union select 311 union select 313
union select 317 union select 331 union select 337 union select 347 union select 349
union select 353 union select 359 union select 367 union select 373 union select 379
union select 383 union select 389 union select 397 union select 401 union select 409
union select 419 union select 421 union select 431 union select 433 union select 439
union select 443 union select 449 union select 457 union select 461 union select 463
union select 467 union select 479 union select 487 union select 491 union select 499
union select 503 union select 509 union select 521 union select 523 union select 541
union select 547 union select 557 union select 563 union select 569 union select 571
union select 577 union select 587 union select 593 union select 599 union select 601
union select 607 union select 613 union select 617 union select 619 union select 631
union select 641 union select 643 union select 647 union select 653 union select 659
union select 661 union select 673 union select 677 union select 683 union select 691
union select 701 union select 709 union select 719 union select 727 union select 733
union select 739 union select 743 union select 751 union select 757 union select 761
union select 769 union select 773 union select 787 union select 797 union select 809
union select 811 union select 821 union select 823 union select 827 union select 829
union select 839 union select 853 union select 857 union select 859 union select 863
union select 877 union select 881 union select 883 union select 887 union select 907
union select 911 union select 919 union select 929 union select 937 union select 941
union select 947 union select 953 union select 967 union select 971 union select 977
union select 983 union select 991 union select 997

________________________________________________ If it is not practically useful, then it is practically useless. ________________________________________________

CREATE TABLE #Numbers
(
Prime INT NOT NULL,
Number BIGINT PRIMARY KEY CLUSTERED
);
DECLARE @Max INT;
SET @Max = 1000000;
WITH n0 AS (SELECT 1 AS p UNION ALL SELECT 1),
n1 AS (SELECT 1 AS p FROM n0 AS a CROSS JOIN n0 AS b),
n2 AS (SELECT 1 AS p FROM n1 AS a CROSS JOIN n1 AS b),
n3 AS (SELECT 1 AS p FROM n2 AS a CROSS JOIN n2 AS b),
n4 AS (SELECT 1 AS p FROM n3 AS a CROSS JOIN n3 AS b),
n5 AS (SELECT 1 AS p FROM n4 AS a CROSS JOIN n4 AS b)
INSERT #Numbers
(
Prime,
Number
)
SELECT f.Prime,
f.Prime * f.Prime AS Number
FROM (
SELECT TOP (1 + @Max / 6)
ROW_NUMBER() OVER (ORDER BY p)
FROM n5
) AS v(Value)
CROSS APPLY (
VALUES (6 * v.Value - 1),
(6 * v.Value + 1)
) AS f(Prime)
WHERE f.Prime <= @Max;
SELECT Prime
FROM (
VALUES (2),
(3)
) AS v(Prime)
WHERE Prime <= @Max
UNION ALL
SELECT n.Prime
FROM #Numbers AS n
WHERE NOT EXISTS (
SELECT *
FROM #Numbers AS p
WHERE p.Number <= n.Prime
AND n.Prime % p.Prime = 0
)
DROP TABLE #Numbers;