Archive

Archive for March, 2011

ASieve of Atkin prime number generator using TSQL

March 31st, 2011 No comments

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
Categories: Project Euler, TSQL Tags:

Project Euler Problem 37 Solution in TSQL

March 28th, 2011 No comments

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
Categories: Project Euler Tags:

Project Euler Problem 61 Solution in TSQL

March 27th, 2011 No comments
/*
	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?

Categories: Project Euler Tags: