Post date: Apr 19, 2014 12:20:55 AM
"What is the largest prime factor of 600851475143?"
We only need to calculate half the factors, up to the SQRT of 600851475143. The other numbers, such as 71 and 8462696833, are paired, so we only need to calculate up to about 1 million. This gives all the factors, prime or otherwise. Each of the numbers in "otherwise" can itself be broken down into factors from that list. So to test against prime, we only need to check against a list of 14 numbers, not the full set, which is a great time saver.
DECLARE @Max bigint = 600851475143
CREATE TABLE #Integers (i bigint PRIMARY KEY CLUSTERED NOT NULL)
INSERT INTO #Integers VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
CREATE TABLE #Factors (i bigint PRIMARY KEY CLUSTERED NOT NULL)
-- Put 1 million integers into a table
INSERT INTO #Integers
SELECT o.i + 10 * t.i + 100 * h.i + 1000 * k.i + 10000 * k10.i + 100000 * k100.i
FROM #Integers o
CROSS JOIN #Integers t
CROSS JOIN #Integers h
CROSS JOIN #Integers k
CROSS JOIN #Integers k10
CROSS JOIN #Integers k100
WHERE o.i + 10 * t.i + 100 * h.i + 1000 * k.i + 10000 * k10.i + 100000 * k100.i >= 10
-- Populate the table with all the numbers that evenly divide into the big number. Get the other half with simple algebra.
INSERT INTO #Factors
SELECT i
FROM #Integers
WHERE i > 1
AND @Max % i = 0
AND i < SQRT(@Max) + 1
UNION
SELECT @Max/i
FROM #Integers
WHERE i > 1
AND @Max % i = 0
AND i < SQRT(@Max) + 1
-- Find the primes
SELECT MAX(i)
FROM #Factors f
WHERE NOT EXISTS (SELECT 1
FROM #Factors f2
WHERE f.i % f2.i = 0
AND f2.i <> f.i)
DROP TABLE #Integers
DROP TABLE #Factors