Thinking outside the box

Patron Saint of Lost Yaks
posts - 203, comments - 734, trackbacks - 4

My Links

Advertisement

News

Archives

Post Categories

Fast and Simple Prime Number Factorization

This algorithm requires an existing Prime numbers table. You can easily create one of your own or importing the primes ranging from 2 to 3,037,000,493 from the Internet. If you only is interested in primes with INT range {2..2,147,483,647} you only need the first 4,792 primes {2..46,337}


DECLARE @Number BIGINT
 
SET     @Number = 2020208534430421
 
SELECT  Prime AS Number,
        CAST(1 AS TINYINT) AS Items
INTO    #Temp
FROM    Primes
WHERE   Prime <= SQRT(@Number)
        AND @Number % Prime = 0

SELECT  @Number = @Number / Number
FROM    #Temp
WHILE @@ROWCOUNT > 0
    UPDATE  #Temp
    SET     Items = Items + 1,
            @Number = @Number / Number
    WHERE   @Number % Number = 0

SELECT  Number,
        Items
FROM    #Temp

UNION ALL

SELECT  @Number,
        1
WHERE   @Number > 1

DROP TABLE    #Temp

And as a function

CREATE FUNCTION dbo.fnPrimeFact
(
    @Number INT
)
RETURNS @Output TABLE
        (
            Prime INT PRIMARY KEY CLUSTERED,
            Items TINYINT NOT NULL
        )
AS
BEGIN
    INSERT  @Output
            (
                Prime,
                Items
            )
    SELECT  Prime,
            1 AS Items
    FROM    dbo.Primes
    WHERE   Prime <= SQRT(@Number)
            AND @Number % Prime = 0
 
    SELECT  @Number = @Number / Prime
    FROM    @Output
 
    WHILE @@ROWCOUNT > 0
        UPDATE  @Output
        SET     Items = Items + 1,
                @Number = @Number / Prime
        WHERE   @Number % Prime = 0
 
    IF @Number > 1
        INSERT  @Output
                (
                    Prime,
                    Items
                )
        VALUES (
                    @Number,
                    1
                )
 
    RETURN
END

Print | posted on Sunday, August 02, 2009 2:12 AM | Filed Under [ SQL Server 2008 Algorithms SQL Server 2005 SQL Server 2000 ]

Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET