Post date: Oct 02, 2014 11:28:54 PM
"Find the minimum four consecutive integers that each have four distinct prime factors, and give the first number of the four."
This is pretty simple, mostly because the answer happens to be fairly small. If I have to factor millions of primes, well, I'm pretty sure it'll never be fast but I'd have to make it more efficient than this simple query.
CREATE TABLE #Integers (i INT PRIMARY KEY NOT NULL)
INSERT INTO #Integers VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers(i) AS
(
SELECT 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
WHERE k100.i < 5
)
INSERT INTO #Integers
SELECT i
FROM Integers
WHERE i >= 10
DELETE FROM #Integers WHERE i = 0
-- Prime Sieve, we know it well.
CREATE TABLE #Primes (i INT PRIMARY KEY NOT NULL)
INSERT INTO #Primes
SELECT i
FROM #Integers
WHERE i > 1
DECLARE @num int = 1
DECLARE @max int SELECT @max = MAX(i) FROM #Primes -- I always forget to change this limit when I copy/paste, so I'll look it up.
WHILE 1 = 1
BEGIN
SELECT @num = MIN(i)
FROM #Primes
WHERE i > @num
IF @num > SQRT(@max)
BREAK
DELETE FROM #Primes
WHERE i % @num = 0
AND i > @num
END -- While
-- Capture a table of distinct factors (both prime and nonprime) in a table.
CREATE TABLE #Factors (i INT NOT NULL, f INT NOT NULL, PRIMARY KEY (i, f))
INSERT INTO #Factors (i, f)
SELECT DISTINCT i.i, factors.f
FROM #Integers i
CROSS APPLY (
-- We can limit this half to just the primes and save a little time.
SELECT f1.i
FROM #Primes f1
WHERE i.i % f1.i = 0
AND f1.i <= SQRT(i.i)
UNION
-- We can't limit this, because some results where f2 is not prime produce i/f2 that IS prime
SELECT i.i/f2.i
FROM #Integers f2
WHERE i.i % f2.i = 0
AND f2.i <= SQRT(i.i)
) factors (f)
-- Delete the non-prime factors that we captured in the bottom half of that last query
DELETE FROM #Factors
WHERE f NOT IN (SELECT i FROM #Primes)
-- From a list of numbers with exactly 4 prime factors, inner join 4 times to itself to get 4 sequential results.
; WITH Factors AS
(
SELECT i
FROM #Factors
GROUP BY i
HAVING COUNT(*) = 4
)
SELECT MIN(f1.i)
FROM Factors f1
INNER JOIN Factors f2
ON f2.i = f1.i + 1
INNER JOIN Factors f3
ON f3.i = f2.i + 1
INNER JOIN Factors f4
ON f4.i = f3.i + 1
DROP TABLE #Integers
DROP TABLE #Factors
DROP TABLE #Primes