Project Euler 003 – TSQL

17 02 2011

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

–The prime factors of 13195 are 5, 7, 13 and 29.

–What is the largest prime factor of the number 600851475143?

 

— this number is bigger than my database

— so we will add it

CREATE PROCEDURE [dbo].[FactorNumber]

       @number AS BIGINT,

       @originalnumber AS BIGINT

AS

 

DECLARE @isPrime BIT

SET @isPrime = 1

 

DECLARE @factor BIGINT

SET @factor = FLOOR(SQRT(@number))

 

DECLARE @divisor BIGINT

 

WHILE @factor > 1

BEGIN

       IF @number % @factor = 0

       BEGIN

              EXEC FactorNumber @factor, @originalnumber

              — can’t do the math in the function call

              — so I used another variable

              SET @divisor = @number / @factor

              EXEC FactorNumber @divisor, @originalnumber

              SET @isPrime = 0

       END

      

       SET @factor = @factor 1

END

 

— here we store the information for later

IF @isPrime = 1

BEGIN

       INSERT INTO NumberFactor  (number, factor) VALUES (@originalnumber, @number)

END

 

–here are the remaining steps to get the answer

–exec FactorNumber 600851475143, 600851475143

–select MAX(factor) from NumberFactor where number = 600851475143

 

 

Discussion

I’ve included the procedure and the select statement here because this number exceeded my number list.  It follows the same philosophy as some of the previous examples except that it inserts its values into a table instead of returning them to the calling function.  This is why we need to pass the original number in as well.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: