## 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.