SQL Server Puzzle:Prime Numbers 9

[SQLDenis]

Why wait until Friday
Okay here we go
This is what needs to be accomplished
Write SQL code that will put all Prime numbers between 1 and 1000000 ( 1 million) into a table and then select a count from that table

Rules
1 You have to write everything from scratch, meaning we should be able to execute the script on any computer and get the same result
2 Don't show any code until the 20th (Next Friday)
3 We should only show the time and recordcount so that people will have a general idea if their code is fast enough
example PIV 3.0 Ghz 2GB RAM runtime 21 seconds recordcount 567
People should post this every time they improve their code so that we can see what's going on
4 The first five people who sign up will run all the scripts and list the in execution time order or we can designate 5 people it doesn't matter
5 remember the fastest time wins, it doesn't have to look pretty


template below

declare @d datetime,@d2 datetime
select @d = getdate()
declare @intPrimeNumberCount int
select @intPrimeNumberCount =0

/*
All other code goes here
*/

select @d2 = getdate()
select (@d2 -@d)as TimeElapsed,@intPrimeNumberCount as PrimeNumberCount

So this is a real SQL puzzle and no admin stuff here
Let me know what you think and good luck


Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[vongrunt]

And here is T-SQL quickie:

declare @N int; set @N = 1000
set rowcount @N
select identity(int, 2, 1) as N into #blah from master..sysobjects A, master..sysobjects B
delete A from #blah A inner join #blah B on A.N % B.N = 0 and B.N < A.N where B.N <= SQRT(@N)
select * from #blah
drop table #blah

Don't - or better said, DON'T - run it with @N above 10,000.
(ya have been warned).


------
"There's a man... He's bald and wears a short-sleeved shirt, and somehow he's very important to me. I think his name is Homer."
(Jack O'Neill, Stargate)

 

[gmmastros]

There's a trick that I show in the VB code, that may be a big help. Notice that I loop through the array to determine the primes.

[!] While i < 1000[/!]

You can stop checking when you are at the square root of the number you want to check. Mathematically, I'm not sure why this is true, but it was suggested on some web page I was looking at.

Also, notice that I am only using prime numbers to check the other numbers. This greatly reduces the time also (because we are checking a lot less numbers). Think about it for a minute. 3 is a prime number. So you elminate all numbers that are evenly divisible by 3 (but greater than 3). 9 is not a prime number. If a number is evenly divisible by 9, it will also be evenly disvisible by 3. So you don't need to check the 9's. 27 is evenly divisible by 9, but it was already taged as 'not prime' by the 3.

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom

 

[SQLDenis]

Plain vanilla Eratosthenes haha

Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[gmmastros]

Here's my stored procedure.

ALTER   Procedure GetPrimeNumbers_gmmastros
As
SET NOCOUNT ON
Create Table #T(Number Integer Identity (3,2) Primary Key, IsPrime Bit)
Set Identity_Insert #T On
Insert Into #T(Number, IsPrime) Select 2, 1 Union All Select 3, 1
Set Identity_Insert #T Off

Insert Into #T(IsPrime)
Select	Top 499998 
		A.IsPrime
From	#t A, #t B, #T C, #T D, #T E, #T F, #T G, #T H, #T I, #T J, #T K, #T L, #T M, #T N, #T O, #T P, #T Q, #T R, #T S

Declare @i Integer
Declare @Test Integer
Set @i = 3

While @i < 1000
	Begin
		Delete 	#T
		Where	Number > @i 
				And Number % @i = 0

		Select	@i = Min(Number)
		From	#T
		Where	Number > @i
	End

Select 	Number As PrimeNumber
From 	#T 
Order By PrimeNumber

Drop Table #T

I set up a temp table with identity column. I force 2 and 3 in to the table (with the indentity insert stuff), and then add 499,998 more records. So, the only even number in the number table is 2, which is the only even number that is prime. After that, it's vanilla Eratosthenes.

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom

 

[pwilson]

Here is mine

Found the Table generation from this site. Modded it to be from
n^2 to n^n with a limit so i wouldnt be joining 100000 twice.

#t is numbers 1 to @NumRows
#j is numbers 1 to SQRT(@NumRows)

This is because of the following
in the list 1,2,3,4,5,6 if you delete the multiples of 2 then you have
1,2,3,5
So if we are looking at 1-10000
100*100 = 10000
So we have to check from 1-100
this is because any Numbers that are not prime above the SQRT will be in the form a*b where a>100 and b<100
if b is below 100 we checked it and deleted it out earlier

ex
5000 doesnt need to be checked, because it was deleted when we checked for multiples of 2


I added in the delete %2 OR %3 OR %5 ... %11 to cut down on the join after that.

On my machine it did the table generation in 5-6 seconds and the delete/join in 10-25 secs.
It averaged around 25 secs total for a number of trials

I found that @Throttle ~ 1000 worked best. Otherwise the table generation wouli take too long.

CREATE   PROCEDURE pwilson_Join
(@NumRows int, @Throttle int, @OUTPUT Decimal(10,5) OUTPUT) 
as

SET NOCOUNT ON

Declare @sqrtNumRows int
SET @sqrtNumRows = SQRT(@NumRows) + 1
Declare @StartTime DateTime
Declare @MidTime DateTime
Declare @EndTime DateTime
Declare @EndTime2 DateTime
Set @StartTime = GetDate()


CREATE TABLE #t (Num int NOT NULL)
CREATE TABLE #j (Num int NOT NULL)


  insert #t values (1)

  while @@ROWCOUNT > 0
    insert #t 
        SELECT S1.Num + S1.MaxRowNum AS Num
            FROM    (           
                  select t.Num,  t.Multiplier * x.MaxRowNum AS MaxRowNum
                        from (SELECT t1.Num, t2.Num AS Multiplier FROM #t t1 FULL OUTER JOIN #t t2 ON t2.Num < @Throttle) AS t
                          cross join
                          (select max (Num) MaxRowNum from #t) x
                  where
                    t.Num <= @NumRows - x.MaxRowNum
            ) AS S1
      where
        S1.Num <= @NumRows - S1.MaxRowNum


  insert #j values (1)

  while @@ROWCOUNT > 0
    insert #j
        SELECT S1.Num + S1.MaxRowNum AS Num
            FROM    (           
                  select t.Num,  t.Multiplier * x.MaxRowNum AS MaxRowNum
                        from (SELECT t1.Num, t2.Num AS Multiplier FROM #j t1 FULL OUTER JOIN #j t2 ON t2.Num < @Throttle) AS t
                          cross join
                          (select max (Num) MaxRowNum from #j) x
                  where
                    t.Num <= @sqrtNumRows - x.MaxRowNum
            ) AS S1
      where
        S1.Num <= @sqrtNumRows - S1.MaxRowNum

Set @MidTime = GetDate()

DELETE FROM #t WHERE Num=1
DELETE FROM #j WHERE Num=1
    DELETE FROM #t WHERE (Num%2=0 AND NOT (Num = 2)) OR (Num%3=0 AND NOT (Num = 3)) OR(Num%5=0 AND NOT (Num = 5)) OR(Num%7=0 AND NOT (Num = 7)) OR(Num%11=0 AND NOT (Num = 11)) OR(Num%13=0 AND NOT (Num = 13))
    DELETE FROM #j WHERE (Num%2=0 AND NOT (Num = 2)) OR (Num%3=0 AND NOT (Num = 3)) OR(Num%5=0 AND NOT (Num = 5)) OR(Num%7=0 AND NOT (Num = 7)) OR(Num%11=0 AND NOT (Num = 11)) OR(Num%13=0 AND NOT (Num = 13))


SET @EndTime = GetDate()

DELETE #t FROM #t t CROSS JOIN #j j WHERE t.Num % j.Num = 0 AND NOT(t.Num = j.Num)

SET @EndTime2 = GetDate()

SET @OUTPUT = Convert(Decimal(10,5), DateDiff(Millisecond, @startTime, Getdate())) / 1000
IF @i = 0
BEGIN
     Select SQRT(@NumRows) SQRT1, Convert(Decimal(10,5), DateDiff(Millisecond, @StartTime, @MidTime)) / 1000 AS Insert1, Convert(Decimal(10,5), DateDiff(Millisecond, @MidTime, @EndTime)) / 1000 AS Insert2, Convert(Decimal(10,5), DateDiff(Millisecond, @EndTime, @EndTime2)) / 1000 AS Delete1, Convert(Decimal(10,5), DateDiff(Millisecond, @EndTime2, Getdate())) / 1000 AS Join1, Convert(Decimal(10,5), DateDiff(Millisecond, @startTime, Getdate())) / 1000 AS Total1
END

DROP TABLE #t
DROP TABLE #j

results

Trial 1     Trial 2     Trial 3     Trial4   Average of the four
16.17000	16.36000	16.42300	19.56300	17.12900
18.17000	16.36000	16.47000	16.18600	16.79650
18.34600	22.64000	22.51300	20.69000	21.04725
20.64000	25.39000	32.26600	46.87300	31.29225
22.20300	23.98600	24.12300	36.79600	26.77700
22.60600	23.34600	20.79600	27.09300	23.46025
26.51600	27.81000	24.36000	23.36000	25.51150
27.17300	31.47000	47.06000	27.55000	33.31325
27.33000	27.32600	27.90600	24.43600	26.74950
28.00000	27.53000	27.68600	27.43600	27.66300
28.01600	27.57600	30.06300	46.11000	32.94125
29.83000	52.62300	27.78000	27.58000	34.45325
30.06000	24.48300	23.58000	23.28000	25.35075
30.84300	52.67300	27.51300	27.87600	34.72625

exec pwilson_Join "1000000","975", @time4 OUTPUT

 

[pwilson]

My eratosthenes took about 10 secs longer than that
replacing the Join part with

DECLARE @i int
SET @i = 2
WHILE @i < SQRT(@NumRows)
BEGIN
    DELETE FROM #t WHERE RowNum%@i=0 AND RowNum > @i
        SET  @i = (SELECT MIN(RowNum) FROM #t where RowNum>@i)
END

 

[SQLDenis]

pwilson I changed

SET @OUTPUT = Convert(Decimal(10,5), DateDiff(Millisecond, @startTime, Getdate())) / 1000
IF @i = 0
BEGIN
     Select SQRT(@NumRows) SQRT1, Convert(Decimal(10,5), DateDiff(Millisecond, @StartTime, @MidTime)) / 1000 AS Insert1, Convert(Decimal(10,5), DateDiff(Millisecond, @MidTime, @EndTime)) / 1000 AS Insert2, Convert(Decimal(10,5), DateDiff(Millisecond, @EndTime, @EndTime2)) / 1000 AS Delete1, Convert(Decimal(10,5), DateDiff(Millisecond, @EndTime2, Getdate())) / 1000 AS Join1, Convert(Decimal(10,5), DateDiff(Millisecond, @startTime, Getdate())) / 1000 AS Total1
END

DROP TABLE #t
DROP TABLE #j

to

SET @OUTPUT = Convert(Decimal(10,5), DateDiff(Millisecond, @startTime, Getdate())) / 1000
IF @OUTPUT = 0
BEGIN
     Select SQRT(@NumRows) SQRT1, Convert(Decimal(10,5), DateDiff(Millisecond, @StartTime, @MidTime)) / 1000 AS Insert1, Convert(Decimal(10,5), DateDiff(Millisecond, @MidTime, @EndTime)) / 1000 AS Insert2, Convert(Decimal(10,5), DateDiff(Millisecond, @EndTime, @EndTime2)) / 1000 AS Delete1, Convert(Decimal(10,5), DateDiff(Millisecond, @EndTime2, Getdate())) / 1000 AS Join1, Convert(Decimal(10,5), DateDiff(Millisecond, @startTime, Getdate())) / 1000 AS Total1
END
select * from #t
DROP TABLE #t

DROP TABLE #j

because it was complaining about the @i


Anyway I ran pwilson proc and gmastros proc 5 times and disregarded the first result

here we go

gmmastros 26s,26s,26s,25s
pwilson 23s,22s,27s,21s

Other people feel free to run the procs and let's see what times you get

Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[vongrunt]

Here is my code:

alter procedure GetPrimeNumbers_vongrunt @primeCount int OUTPUT
as
set nocount on

-- general purpose variable(s)
declare @i int

-- 10-digit table
declare @D table (N int)
insert into @D (N) select 0 union all select 1 union all select 2 union all select 3 union all select 4
insert into @D (N) select N+5 from @D

-- build small sieve table [2... 1000]
declare @T table (N int)
insert into @T( N )
select 1+A.N+10*(B.N+10*C.N)
from @D A, @D B, @D C

delete from @T where N = 1

set @i = 2
while @i <= SQRT(1000)
begin
	delete from @T where N % @i = 0 and N > @i
	set @i = @i + 1
end

-- generate large table [1001...1000000]
select A+10*(B+10*(C+10*(D+10*(E+ 10*F)))) as N
into #P
from
(	select A.N as A, B.N as B, C.N as C, D.N as D, E.N as E, F.N as F
	from @D A, @D B, @D C, @D D, @D E, @D F
	where A.N in (1, 3, 7, 9)  -- not divisible by 2 or 5
) blah
where (A+B+C+D+E+F) % 3 <> 0 -- or 3
	and (A+3*B+2*C-D-3*E-2*F) % 7 <> 0 -- or 7
	and (B-A+D-C+F-E) % 11 <> 0 -- or 11
	and D|E|F <> 0 -- not first 1000 numbers, we'll already have these in small sieve
union all select 1000000

-- sieve that table with smaller one
select @i = 2 -- let's be fair :) and not start with 13
while @i is not null
begin
	delete from #P where N% @i = 0
	select @i = min(N) from @T where N > @i
end

-- add primes up to 1000
insert into #P select N from @T

-- voila
select @primeCount = count(*) from #P

drop table #P
go

Sample call:

declare @startTime datetime, @endTime datetime, @primeCount int
set @startTime = getDate()

exec GetPrimeNumbers_vongrunt @primeCount output

set @endTime = getDate()
select @primeCount as primeCount, DateDiff(ms, @startTime, @endTime)/ 1000. as TimeElapsed

------
"There's a man... He's bald and wears a short-sleeved shirt, and somehow he's very important to me. I think his name is Homer."
(Jack O'Neill, Stargate)

 

[SQLDenis]

Okay vongrunt's proc ran in these times

5.93s 6.07s 5.79s 5.93s and yes these are seconds

So below 6 seconds exept for 1 run

Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[SQLDenis]

Any more or is it time for the star awards ceremony?

And winner has to come up with new puzzle of course

Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[earthandfire]

On a PIII 1.1Ghz laptop with 512 Ram using QA each tested 10 times, worst times were:

vongrunt 17 secs
gmmastros 49 secs
pwilson 1 min 34 secs

best times:

vongrunt 16 secs
gmmastros 27 secs
pwilson 44 secs

 

[SQLDenis]

On a PIV with 2.8 Hyperthreaded 2GB Ram workstation the times are

I disregarded the first run because of plan compilation etc

Worst
vongrunt 6.07 secs
gmmastros 26 secs
pwilson 27 secs

best times:

vongrunt 5.93 secs
pwilson 21 secs
gmmastros 25 secs




Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[SQLDenis]

Stars for all 3 answers
Now vongrunt, where is the next puzzle?

Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[SQLDenis]

And vongrunt, nothing with dates please

Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[DotNetGnat]

Okay vongrunt's proc ran in these times
5.93s 6.07s 5.79s 5.93s and yes these are seconds

amazing vongrunt...

George and pwilson...good job...

stars for you all...

-DNG

 

[gmmastros]

I enjoyed this puzzle. It was very challenging. Stars to vongrunt and pwilson.

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom

 

[dbomrrsm]

Von

Havent been here for a while but you dont stop amazing me. A star for sure.

Great code as usual and well done to the others.



[blue]DBomrrsm[/blue]

[blue]Software code, like laws and sausages, should never be examined in production[/blue][black] - [/black][purple]Edward Tenner[/purple]