31Mar/110

## ASieve of Atkin prime number generator using TSQL

I worked out an implementation of the Sieve of Atkin for use in solving Project Euler problems. It's probably not as efficient as it could be, but it does the trick for me.

set nocount on drop table #atkin create table #atkin ( num float , isPrime bit ) create clustered index primenums on #atkin(num) declare @limit as bigint declare @sqrt as float declare @x as int declare @y as int declare @n as int set @limit = 1000000 set @sqrt = sqrt(@limit) set @x = 1 print 'begin outer loop' /* put in candidate primes: integers which have an odd number of representations by certain quadratic forms */ while (@x <= @sqrt) begin set @y = 1 while (@y <=@sqrt) begin set @n = (4 * (@x * @x)) + (@y * @y) if ((select num from #atkin where num =@n) is null) insert into #atkin (num, isPrime) values (@n,0) if (@n <= @limit AND (@n % 12 = 1 or @n % 12 =5)) update #atkin set isPrime = isPrime ^ 1 where num = @n set @n = (3 * (@x * @x)) + (@y * @y) if ((select num from #atkin where num =@n) is null) insert into #atkin (num, isPrime) values (@n,0) if (@n <= @limit AND @n % 12 = 7) update #atkin set isPrime = isPrime ^ 1 where num = @n set @n = (3 * (@x * @x)) - (@y * @y) if ((select num from #atkin where num =@n) is null) insert into #atkin (num, isPrime) values (@n,0) if (@x >= @y AND @n <= @limit AND @n % 12 = 11) update #atkin set isPrime = isPrime ^ 1 where num = @n set @y = @y + 1 end set @x = @x + 1 end declare @nsqr as bigint declare @k as bigint /* eliminate composites by sieving */ set @n = 5 while ( @n <= @sqrt) begin print @n if ((select isprime from #atkin where num = @n)=1) begin set @nsqr = @n * @n set @k = @nsqr while (@k <= @limit) begin update #atkin set isPrime = 0 where num = @k set @k = @k + @nsqr print '@k increment ' + str(@k) end end set @n = @n + 1 print '@n increment ' + str(@n) end insert into #atkin (num, isPrime) values (2,1) insert into #atkin (num, isPrime) values (3,1) delete from #atkin where isprime <> 1

28Mar/110

## Project Euler Problem 37 Solution in TSQL

This is a solution for Project Euler Problem 37. It makes uses of a temporary table called #atkin which is populated with prime numbers using the TSQL routine that uses the Sieve of Atkin, which is also located on this site.

Easy! There are, however, a couple of deliberate errors, that can be easily located with some patience. I donâ€™t want to make things to easy for you little scamps, do I?

/* process the prime number list */ /* the number we are examining can't be single digits or contain zeros */ drop table #candidates select num into #candidates from #atkin where charindex('0', cast(num as varchar)) = 0 declare @ctr as integer declare @del as integer set @ctr = 1 set @del = 0 /* delete from the candidate list any number that doesn't have a shorter counterpart in the list of prime numbers, increasing the string size by 1 with every loop, and bailing out of when we stop deleting things */ while (@del > 0) begin delete from #candidates from #candidates c1 left outer join #atkin a1 on left(c1.num,@ctr) = a1.num left outer join #atkin a2 on right(c1.num,@ctr) = a2.num where a1.num is null or a2.num is not null set @del = @@rowCount set @ctr = @ctr + 1 end /* output the answer */ select sum(num) from #candidates

27Mar/110

## Project Euler Problem 61 Solution in TSQL

/* generate the number range */ create table #polygonalnumbers ( ctr int , val bigint , poltype varchar(3) ) declare @ctr as integer set @ctr = 1 while (@ctr < 1000) begin insert into #polygonalnumbers select @ctr,(@ctr*(@ctr+1))/2,'tri' insert into #polygonalnumbers select @ctr,@ctr * @ctr *@ctr,'sqr' insert into #polygonalnumbers select @ctr,(@ctr*((3*@ctr)-1))/2 ,'pnt' insert into #polygonalnumbers select @ctr,(@ctr*((2*@ctr)-1)) ,'hex' insert into #polygonalnumbers select @ctr,(@ctr*((5*@ctr)-3))/2 ,'hep' insert into #polygonalnumbers select @ctr,(@ctr*((3*@ctr)-2)) ,'oct' set @ctr = @ctr + 1 end /* disregard */ delete from #polygonalnumbers where LEN(val) <> 4 /* output the answer */ select distinct num1.val + num2.val + num3.val + num4.val + num5.val + num6.val from #polygonalnumbers num1 inner join #polygonalnumbers num2 on RIGHT (num1.val,2) = LEFT(num2.val,1) and num2.poltype <> num1.poltype inner join #polygonalnumbers num3 on RIGHT (num2.val,2) = LEFT(num3.val,2) and num3.poltype <> num2.poltype and num3.poltype <> num1.poltype inner join #polygonalnumbers num4 on RIGHT (num3.val,2) = LEFT(num4.val,2) and num4.poltype <> num3.poltype and num4.poltype <> num2.poltype and num4.poltype <> num1.poltype inner join #polygonalnumbers num5 on RIGHT (num4.val,2) = LEFT(num5.val,2) and num5.poltype <> num4.poltype and num5.poltype <> num3.poltype and num5.poltype <> num2.poltype and num5.poltype <> num1.poltype inner join #polygonalnumbers num6 on RIGHT (num5.val,2) = LEFT(num6.val,2) and num6.poltype <> num5.poltype and num6.poltype <> num4.poltype and num6.poltype <> num3.poltype and num6.poltype <> num2.poltype and num6.poltype <> num1.poltype and RIGHT (num6.val,2) = LEFT(num1.val,2)

Easy! There are, however, a couple of deliberate errors, that can be easily located with some patience. I don't want to make things to easy for you little scamps, do I?