Get your favorite SSC scripts directly in SSMS with the free SQL Scripts addin. Search for scripts directly from SSMS, and instantly access any saved scripts in your SSC briefcase from the favorites tab.
Download now (direct download link)

Table Valued Function to factorize numbers up to 100 trillion

By Jonathan Roberts, 2017/04/26

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