Post date: Oct 28, 2014 11:53:47 PM
"What prime number under 1 million is equal to the sum of the greatest number of consecutive prime numbers?"
-- Generate primes to 1 million, with an added column to be used as a rowcount
CREATE TABLE #Primes (i int not null primary key, c int null)
INSERT INTO #Primes (i) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers(i) AS
(
SELECT o.i +
(10 * d.i) +
(100 * h.i) +
(1000 * k.i) +
(10000 * k10.i) +
(100000 * k100.i)
FROM #Primes o
CROSS JOIN #Primes d
CROSS JOIN #Primes h
CROSS JOIN #Primes k
CROSS JOIN #Primes k10
CROSS JOIN #Primes k100
)
INSERT INTO #Primes (i)
SELECT i
FROM Integers
WHERE i >= 10
DELETE FROM #Primes WHERE i < 2
DECLARE @max int
SELECT @max = MAX(i) FROM #Primes
DECLARE @num int = 1
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
-- Add an incremented fields, so we can tell what primes are perfectly sequential
; WITH Counter (i, c) AS
(
SELECT i, ROW_NUMBER() OVER (ORDER BY i)
FROM #Primes
)
UPDATE p
SET c = c.c
FROM #Primes p
INNER JOIN Counter c
ON c.i = p.i
-- We know that there are more than 21 terms, because the problem gives an example of 953, which is the sum of 21 primes
-- The answer will probably be near the max, because a higher number can be the sum of more numbers.
-- So let's calculate numbers up to 1 million divided by 21, or roughly 50000. This handles the worst case, which is 22 of the biggest numbers.
-- The total in this query is a running total directed by the rowcount field added in the previous step.
; WITH PrimeSequences (start, prime, sequenceLength, total) AS
(
SELECT p1.i
, p2.i
, p2.c - p1.c + 1
, SUM(p2.i) OVER (PARTITION BY p1.i ORDER BY p2.i ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
FROM #Primes p1
INNER JOIN #Primes p2
ON p2.c >= p1.c
WHERE p1.i < 50000
AND p2.i < 50000
)
SELECT TOP 1 total
FROM PrimeSequences
WHERE total IN (SELECT i FROM #Primes)
ORDER BY sequenceLength desc
DROP TABLE #Primes