Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums
 General SQL Server Forums
 Script Library
 Prime Number Table Function

Author  Topic 

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-26 : 12:29:41
Creates a table of prime numbers, starting at 2 up to a maximum number.

Makes use of dbo.F_TABLE_NUMBER_RANGE, which is found here:
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=47685

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
Can we improve on the speed?



Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2006-07-26 : 12:41:07
It should be faster to use the Sieve of Eratosthenes algorithm.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

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
Go to Top of Page

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-26 : 12:53:59
quote:
Originally posted by Michael Valentine Jones

It should be faster to use the Sieve of Eratosthenes algorithm.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

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?


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.
Go to Top of Page

nr
SQLTeam MVY

12543 Posts

Posted - 2006-07-26 : 14:49:46
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.
Go to Top of Page

byrmol
Shed Building SQL Farmer

1591 Posts

Posted - 2006-07-26 : 20:02:17
It was a while ago but this was my take on it..

http://weblogs.sqlteam.com/davidm/archive/2003/10/30/412.aspx





DavidM

Intelligent Design is NOT science.

A front-end is something that tries to violate a back-end.
Go to Top of Page

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2006-07-26 : 23:19:22
Ryan,

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
Go to Top of Page

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-27 : 05:01:45
Nice work, Michael. Thanks

Where did Peso's post go? Peso?


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.
Go to Top of Page

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2006-07-27 : 07:20:20
quote:
Originally posted by RyanRandall

Nice work, Michael. Thanks

Where did Peso's post go? Peso?


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.



Did you happen to try them to see it you get similar run-times? I only tried my code on my old desktop computer, not a server.



CODO ERGO SUM
Go to Top of Page

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-27 : 08:08:07
Here's my latest effort.

It's a direct implementation of algorithm for the "sieve of Aitken", as described here: http://en.wikipedia.org/wiki/Prime_number

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'm still working on improving this...


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.
Go to Top of Page

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-27 : 10:45:32
Here's a minor improvement (I think)...

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


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.
Go to Top of Page

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2006-07-27 : 11:42:17
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
Go to Top of Page

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-27 : 12:27:53
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.


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-27 : 13:29:59
Changing
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
slashed 10% of the time for me...


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

7020 Posts

Posted - 2006-07-27 : 14:39:53
quote:
Originally posted by RyanRandall

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.


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.



So to find all the prime numbers up to 1,000,000, do you still pass a value of @MaxNumber = 1,000,000?

CODO ERGO SUM
Go to Top of Page

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-28 : 05:03:15
quote:
Originally posted by Peso

Changing
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
slashed 10% of the time for me...

Peter Larsson
Helsingborg, Sweden

Nice one Peso

Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.
Go to Top of Page

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-28 : 05:11:03
quote:
So to find all the prime numbers up to 1,000,000, do you still pass a value of @MaxNumber = 1,000,000?
Yeah, that's right. That's the 'sieve of Atkin' algorithm, not that I knew before this week.

I've just realised I spelled Atkin wrong earlier (not sure where I copied it from), so apologies to Professor Atkin.

I also think I haven't quite got the last bit of the algorithm right yet (sigh).


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-29 : 07:57:40
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


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-30 : 15:26:36
This is my function.
If anyone is interested, I can post the findings of this algorithm here.
CREATE FUNCTION	dbo.fnIsPrime
(
@Number INT
)
RETURNS BIT
AS

BEGIN
IF @Number < 2
RETURN 0

IF @Number % 10 IN (0, 2, 4, 5, 6, 8)
RETURN CASE WHEN @Number IN (2, 5) THEN 1 ELSE 0 END

DECLARE @PseudoPrimes BIGINT,
@PseudoPrime BIGINT,
@IsPrime BIT

SELECT @PseudoPrime = 1,
@PseudoPrimes = (SQRT(@Number) - 1) / 2,
@IsPrime = 1,
@Number = (@Number - 1) / 2

WHILE @PseudoPrime <= @PseudoPrimes
IF (@Number - 2 * @PseudoPrime * @PseudoPrime - 2 * @PseudoPrime) % (2 * @PseudoPrime + 1) = 0
BEGIN
SELECT @IsPrime = 0
BREAK
END
ELSE
SELECT @PseudoPrime = @PseudoPrime + 1

RETURN @IsPrime
END

Peter Larsson
Helsingborg, Sweden
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-07-27 : 23:41:13
[code]/* 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
)[/code]


N 56°04'39.26"
E 12°55'05.63"
Go to Top of Page

blindman
Master Smack Fu Yak Hacker

2365 Posts

Posted - 2009-07-28 : 10:01:23
[code]
--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
[/code]

________________________________________________
If it is not practically useful, then it is practically useless.
________________________________________________
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2013-03-14 : 10:23:09
[code]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;[/code]


N 56°04'39.26"
E 12°55'05.63"
Go to Top of Page
    Next Page

- Advertisement -