Calculate prime numbers in SQL Server 2005

Thought I would start a challenge.

Who can come up with the best way of calculating prime numbers in SQL server. with all the progamability changes in 2005 there must be a really good way of doing it, or is there.

I've had a few stabs using a CTE and some TSQL put not that impressive, the CTE has limitations, the TSQL produced 1 million prime numbers in 7 minutes.

Can you do better

Heres the some code,

set nocount on
declare @prime table (prime int not null primary key)
--insert into @prime values (2)
--insert into @prime values (3)
--insert into @prime values (5)
--insert into @prime values (7)
--insert into @prime values (11)
declare @number int, @pc int
set @number = 13
set @pc = 1
while @pc < 1000000
begin

   if not exists (select 1 from @prime where @number % prime = 0 and prime < sqrt(@number) )
   begin
      insert into @prime select @number
      set @pc = @pc +1
   end
   set @number = @number
            + case when @number %2 = 1 then 2
                   when @number %3 = 2 then 2
                   when @number %5 = 4 then 2
                   when @number %7 = 6 then 2
                   when @number %11 = 10 then 2
              else 1 end
   end
select @pc

AND

with seq
as( select 13 number
union all
select s.number
+ case when s.number %2 = 1 then 2
when s.number %3 = 2 then 2
when s.number %5 = 4 then 2
when s.number %7 = 6 then 2
when s.number %11 = 10 then 2
else 1 end
from seq s
where number < 32767
)
, prime as (
select s.number
from seq s
where not exists ( select 1 from seq s2 where s2.number < s.number and (s.number) % s2.number = 0)
)
select *
from prime
option (MAXRECURSION 32767)

-
Published 28 June 2005 13:18 by simonsabin

Comments

04 December 2010 09:41 by Razvan Socol

# re: Calculate prime numbers in SQL Server 2005

Your code is wrong for multiple reasons:

1. Both versions do not insert the first values (2, 3, 5, 7, 11) and as a result a lot of numbers are declared prime although they are not; in the iterative version, we just uncomment those lines (and set the initial value of @pc to 5 instead of 1); in the recursive version, it's more complicated (see below).

2. The iterative version says the square of prime numbers (for example 25) is a prime number, although it is not; we need to replace "prime < sqrt(@number)" with "prime <= sqrt(@number)".

3. In both versions, the incrementing of @number is unnecessarily complicated: the current version just adds 2 always, because number%2 will always be 1 when we add 2 to an odd number.

If we want a more complicated incrementing (which is somewhat more efficient), we can use:

  set @number = @number +

    case

when @number%3=1 then 4

when @number%5=3 then 6

when @number%7=5 then 6

when @number%11=9 then 6

when @number%13=11 then 6

when @number%17=15 then 6

    else 2 end

(I have no formal proof that it's correct, but it seems to return the correct values; at least the 100000'th prime is correct: 1299709).

For the recursive version, we could write:

with seq

as( select 2 number

union all

select s.number +

    case

when s.number%2=0 then 1

when s.number%3=1 then 4

when s.number%5=3 and s.number>5 then 6

when s.number%7=5 and s.number>7 then 6

when s.number%11=9 and s.number>11 then 6

when s.number%13=11 and s.number>13 then 6

when s.number%17=15 and s.number>17 then 6

    else 2 end

from seq s

where number < 32767

)

, prime as (

select s.number

from seq s

where not exists ( select 1 from seq s2 where s2.number*s2.number <= s.number and (s.number) % s2.number = 0)

)

select *

from prime

option (MAXRECURSION 32767)

Unfortunately, this is still much slower than the iterative version...