Project Euler problem 3 T-SQL Find Prime factors

Posted on

Project Euler Problem 3 is: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? I thought of finding prime numbers and try to divide the number 600851475143 with them and then check if I found all the factors and finding the biggest one.
For finding primes quickly under 10 millions Sieve of Eratosthenes is wellknown algorithm that has been around for 2500 years. ( What I do not understand of the algorithm is that I only have to check up to the square root of the number serie see row 23. If I hade done this myself I would have looped till then of the list of numbers I am checking )

Image of greek mathematician Eratosthenes

Portrait of Eratosthenes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

USE tempdb
SET NOCOUNT ON 
DECLARE @IntSeq  AS TABLE (j int IDENTITY(1,1)
        PRIMARY KEY clustered ,	isPrime BIT DEFAULT 0 )
DECLARE @n INT,@p INT,@j INT  ,@ToFactor BIGINT
SET @n=10000;
--pull upp integer sequence with 10000 rows
-- I grab 100 rows and cross join them to get 
-- the rows I think suffice. Cross join is more then  20 times 
--faster then a while loop for this number grabbing
WITH NumRange (num_int) AS
(SELECT TOP 100 ROW_NUMBER()OVER (ORDER BY object_id)
  FROM sys.columns) 
  INSERT  @IntSeq (isPrime)
SELECT  1 
    FROM NumRange one CROSS JOIN NumRange sqr  ; 
 
    -- 1 is not a prime   
UPDATE @IntSeq SET isPrime=0 WHERE j=1
    -- Find primenumbers less then @n with  
    -- the Sieve of Eratosthenes
UPDATE @IntSeq SET isPrime=0 WHERE j=1
SET @p=2
  while SQUARE(@p)  <  @n 
  BEGIN
	SET @j = SQUARE(@p)
 
      while (@j =<  @n) 
       BEGIN
	UPDATE @IntSeq SET isPrime=0 WHERE j=@j
	    SET @j += @p
        END   
	    SELECT @p=MIN(j) 
            FROM  @IntSeq 
            WHERE isPrime=1 AND j<@p   
   END
  -- End the Sieve of Eratosthenes
   -- now list good candidates for biggest primefactor
SET @ToFactor = 600851475143 
SELECT j,LOG(j)[Log of j] FROM @IntSeq 
WHERE isPrime=1 AND @ToFactor%j=0
ORDER BY j DESC
-- if sum of logs and log(600851475143) are same then
-- product of all factors I found are the same
SELECT SUM(LOG(j))-LOG(@ToFactor)IfZeroAllFactorAreFound 
FROM @IntSeq WHERE isPrime=1 AND @ToFactor%j=0

My senior colleague Tomas solution solves the problem in a single select and with brute force. I liked the triangulare join at the end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

 --Find the largest prime factor of a composite number.
USE tempdb;
GO
 
DECLARE @composite  bigint = 600851475143;
 
     -- Create a numbers table 
     -- Max available composite depends on the number 
     -- of objects in the database, ~27M in my case.
     -- Add another cross join if one wants REALLY large numbers 
WITH Numbers_CTE AS    
     (
     SELECT ROW_NUMBER() OVER (ORDER BY sc1.object_id) AS number
      FROM  
      sys.all_columns AS sc1 
      CROSS JOIN 
      sys.all_columns AS sc2
      --CROSS JOIN 
        --    sys.all_columns AS sc3
          )
    -- Find all numbers that are factors of the input
    -- Brute force...
    ,Factors_CTE AS    (
                        SELECT number
                        FROM  Numbers_CTE 
                        WHERE number     <= @composite
                        AND   @composite % number = 0
                       )
    -- Find the primes among the factors.
    -- Incurs a triangular join, but the main work 
    -- has been done in finding the factors
    ,Primes_CTE AS     
           (
              SELECT f.number
              FROM Factors_CTE AS f
              WHERE NOT EXISTS (SELECT *
                                FROM  Factors_CTE
                                WHERE number < f.number
                                AND   f.number % number = 0
                                AND   <> 1)
                       )
SELECT TOP 1 number AS [largest prime factor] 
FROM Primes_CTE
ORDER BY number DESC;

Reine Lindqvist a senior T-SQL developer contributed with this short and direct solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

use tempdb
go
declare @n       bigint = 600851475143
declare @newnum  bigint = @n;
declare @factors varchar(max) = '';
declare @tryme   bigint = 2;
SELECT top(cast(SQRT(@n) as int)+1)
@factors = CASE WHEN (@newnum % @tryme = 0) THEN cast(@tryme as varchar(20)) ELSE @factors END
,@newnum  = CASE WHEN (@newnum % @tryme = 0) THEN @newnum/@tryme ELSE @newnum END
,@tryme   = CASE WHEN (@newnum % @tryme = 0) THEN @tryme ELSE @tryme + 1 END
FROM sys.all_columns a CROSS JOIN sys.all_columns b
WHERE @tryme*@tryme <= @newnum
SELECT @factors as factors
go