SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 General SQL Server Forums
 Script Library
 Prime Number Table Function
 New Topic  Reply to Topic
 Printer Friendly
Next Page
Author Previous Topic Topic Next Topic
Page: of 2

RyanRandall
Flowing Fount of Yak Knowledge

United Kingdom
1074 Posts

Posted - 07/26/2006 :  12:29:41  Show Profile  Reply with Quote
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)

USA
7020 Posts

Posted - 07/26/2006 :  12:41:07  Show Profile  Reply with Quote
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
Flowing Fount of Yak Knowledge

United Kingdom
1074 Posts

Posted - 07/26/2006 :  12:53:59  Show Profile  Reply with Quote
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

United Kingdom
12543 Posts

Posted - 07/26/2006 :  14:49:46  Show Profile  Visit nr's Homepage  Reply with Quote
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

Australia
1591 Posts

Posted - 07/26/2006 :  20:02:17  Show Profile  Reply with Quote
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)

USA
7020 Posts

Posted - 07/26/2006 :  23:19:22  Show Profile  Reply with Quote
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

Edited by - Michael Valentine Jones on 07/26/2006 23:23:57
Go to Top of Page

RyanRandall
Flowing Fount of Yak Knowledge

United Kingdom
1074 Posts

Posted - 07/27/2006 :  05:01:45  Show Profile  Reply with Quote
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)

USA
7020 Posts

Posted - 07/27/2006 :  07:20:20  Show Profile  Reply with Quote
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
Flowing Fount of Yak Knowledge

United Kingdom
1074 Posts

Posted - 07/27/2006 :  08:08:07  Show Profile  Reply with Quote
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
Flowing Fount of Yak Knowledge

United Kingdom
1074 Posts

Posted - 07/27/2006 :  10:45:32  Show Profile  Reply with Quote
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)

USA
7020 Posts

Posted - 07/27/2006 :  11:42:17  Show Profile  Reply with Quote
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
Flowing Fount of Yak Knowledge

United Kingdom
1074 Posts

Posted - 07/27/2006 :  12:27:53  Show Profile  Reply with Quote
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.

Edited by - RyanRandall on 07/27/2006 12:30:16
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30241 Posts

Posted - 07/27/2006 :  13:29:59  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Edited by - SwePeso on 07/27/2006 13:34:59
Go to Top of Page

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

USA
7020 Posts

Posted - 07/27/2006 :  14:39:53  Show Profile  Reply with Quote
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
Flowing Fount of Yak Knowledge

United Kingdom
1074 Posts

Posted - 07/28/2006 :  05:03:15  Show Profile  Reply with Quote
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
Flowing Fount of Yak Knowledge

United Kingdom
1074 Posts

Posted - 07/28/2006 :  05:11:03  Show Profile  Reply with Quote
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

Sweden
30241 Posts

Posted - 07/29/2006 :  07:57:40  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Edited by - SwePeso on 07/29/2006 08:09:59
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30241 Posts

Posted - 07/30/2006 :  15:26:36  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Edited by - SwePeso on 07/30/2006 19:43:16
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30241 Posts

Posted - 07/27/2009 :  23:41:13  Show Profile  Visit SwePeso's Homepage  Reply with Quote
/* 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
			)



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

blindman
Flowing Fount of Yak Knowledge

USA
2365 Posts

Posted - 07/28/2009 :  10:01:23  Show Profile  Reply with Quote

--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.
________________________________________________

Edited by - blindman on 07/28/2009 10:02:14
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30241 Posts

Posted - 03/14/2013 :  10:23:09  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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;



N 56°04'39.26"
E 12°55'05.63"
Go to Top of Page
Page: of 2 Previous Topic Topic Next Topic  
Next Page
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.2 seconds. Powered By: Snitz Forums 2000