Post date: May 10, 2014 2:24:44 PM
"What is the smallest number divisible by all numbers between one and 20?"
CREATE TABLE #Integers (i BIGINT PRIMARY KEY NOT NULL)
INSERT INTO #Integers VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers(i) AS
(
SELECT 1000000 * m.i + 100000 * k100.i + 10000 * k10.i + 1000 * k.i + 100 * h.i + 10 * t.i + o.i
FROM #Integers o
CROSS JOIN #Integers t
CROSS JOIN #Integers h
CROSS JOIN #Integers k
CROSS JOIN #Integers k10
CROSS JOIN #Integers k100
CROSS JOIN #Integers m
)
INSERT INTO #Integers
SELECT i
FROM Integers
WHERE i >= 10
DELETE FROM #Integers WHERE i = 0
-- 2 * 3 * 4 * 5 ... 20 is this really big number. We know this is divisible by all the numbers, but it's not the smallest.
-- Any smaller number that meets the criteria can be multiplied by something to get this number ... in other words, we only need to check the factors.
-- When we check, we don't have to check the numbers from 2 to 10, because they are factors of those numbers from 11-20 that aren't prime.
DECLARE @BFN BIGINT = 670442572800
; WITH Factors(i) AS
(
-- Return all the factors
SELECT i
FROM #Integers
WHERE CONVERT(bigint,@BFN % i) = 0
AND i < SQRT(@BFN) + 1
UNION
SELECT @BFN/i
FROM #Integers
WHERE CONVERT(bigint,@BFN % i) = 0
AND i < SQRT(@BFN) + 1
),
Answers(i) AS
(
SELECT i
FROM Factors
WHERE i % 11 = 0
INTERSECT
SELECT i
FROM Factors
WHERE i % 12 = 0
INTERSECT
SELECT i
FROM Factors
WHERE i % 13 = 0
INTERSECT
SELECT i
FROM Factors
WHERE i % 14 = 0
INTERSECT
SELECT i
FROM Factors
WHERE i % 15 = 0
INTERSECT
SELECT i
FROM Factors
WHERE i % 16 = 0
INTERSECT
SELECT i
FROM Factors
WHERE i % 17 = 0
INTERSECT
SELECT i
FROM Factors
WHERE i % 18 = 0
INTERSECT
SELECT i
FROM Factors
WHERE i % 19 = 0
INTERSECT
SELECT i
FROM Factors
WHERE i % 20 = 0
)
SELECT MIN(i)
FROM Answers
DROP TABLE #Integers