Table Valued Function to factorize numbers up to 100 trillion

Jonathan Roberts, 2017-04-26 (first published: 2017-04-06)

To use this function you will need a populated table of primes. See script: http://www.sqlservercentral.com/scripts/Prime+Numbers/155286/

Theoretically the maximum number that can be guaranteed to be factorized is the maximum value of a bigint (9223372036854775807) but to guarantee factorisation you will need all primes up to the square root of that value in the dbo.Primes table.

To factorise any number up to 100 trillion you will need a Primes table with all prime less than 10,000,000. To do this use the the script here to generate a table of 10 million primes.

Sampe call to factorise a number:

SELECT * FROM dbo.PrimeFactors(99999820000081)

USE [Test] GO IF OBJECT_ID('[dbo].[PrimeFactors]','TF') IS NULL EXEC('CREATE FUNCTION [dbo].[PrimeFactors]() RETURNS @t TABLE(n int) BEGIN RETURN END') GO -- ***************************************************************** -- Author: Jonathan Roberts -- Create date: 06/04/2017 -- Description: Table Valued Function to return all prime factors of a number. -- Sample Call: -- SELECT * FROM dbo.PrimeFactors(99999820000081*46747) -- 9999991^2* 46747 -- SELECT * FROM dbo.PrimeFactors(99999820000081) -- 9999991^2 -- SELECT * FROM dbo.PrimeFactors(374813281871281219) -- 612219977*612219947 -- SELECT * FROM dbo.PrimeFactors(374813281871281237) -- Prime number -- SELECT * FROM dbo.PrimeFactors(2147483647) -- A mersenne prime (2^31-1) -- ***************************************************************** ALTER FUNCTION dbo.PrimeFactors ( @Number bigint ) RETURNS @Factors TABLE(PrimeFactor bigint NOT NULL PRIMARY KEY CLUSTERED, [Power] int NOT NULL, [Message] varchar(200) NULL) AS BEGIN DECLARE @WorkTable TABLE (PrimeFactor bigint NOT NULL,LoopCounter int NULL) DECLARE @IsPrimeFactorized bit = 0 DECLARE @ProductOfJustFoundPrimeFactors bigint DECLARE @PrimesFound int DECLARE @LoopCounter int = 0 WHILE @IsPrimeFactorized = 0 AND @LoopCounter < 32 BEGIN SET @LoopCounter+=1 INSERT INTO @WorkTable ( PrimeFactor, LoopCounter ) SELECT p.N, @LoopCounter FROM Primes p WHERE p.N <= SQRT(@Number) AND @Number%p.N = 0 SET @PrimesFound = @@ROWCOUNT IF @PrimesFound > 0 BEGIN SET @ProductOfJustFoundPrimeFactors=1 -- Initialise SELECT @ProductOfJustFoundPrimeFactors=@ProductOfJustFoundPrimeFactors*F.PrimeFactor FROM @WorkTable F WHERE F.LoopCounter = @LoopCounter SET @Number = @Number/@ProductOfJustFoundPrimeFactors IF EXISTS(SELECT * FROM dbo.Primes p WHERE p.N = @Number) BEGIN INSERT INTO @WorkTable (PrimeFactor,LoopCounter) VALUES(@Number, 0); SET @IsPrimeFactorized = 1 END END ELSE BEGIN INSERT INTO @WorkTable VALUES(@Number, 0); SET @IsPrimeFactorized = 1 END END --WHILE DECLARE @MaxPrimeThatCanBeFound bigint SELECT @MaxPrimeThatCanBeFound = POWER(MAX(CONVERT(bigint,N)),2) FROM dbo.Primes DECLARE @Msg nvarchar(100)=NULL IF @MaxPrimeThatCanBeFound < @Number SET @Msg=CONCAT('The largest number that can be reliably tested to be prime is ',FORMAT(@MaxPrimeThatCanBeFound,'#,##0')); -- Populate the results INSERT INTO @Factors(PrimeFactor,[Power],[Message]) SELECT F.PrimeFactor,COUNT(*) [Power],@Msg FROM @WorkTable F WHERE F.PrimeFactor > 1 GROUP BY PrimeFactor ORDER BY PrimeFactor RETURN END GO