Post date: Aug 08, 2014 12:38:59 AM
"Find the 11 primes over 10 that, where no matter how many digits are taken off either the right or the left, always remain prime. Sum them."
Really, the only reason this works is that we know there are only 11 two-sided primes. That is how I know I don't have to check numbers for infinity, which would be pretty difficult to do.
CREATE TABLE #Primes (i int not null primary key)
INSERT INTO #Primes (i) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
-- Sieve of Eratosthenes
-- I tried two other prime sieves, ones that were supposed to be faster, but Eratosthenes was the fastest by far. So let's keep going.
; 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 @num int = 1
WHILE 1 = 1
BEGIN
SELECT @num = MIN(i)
FROM #Primes
WHERE i > @num
IF @num > SQRT(999999)
BREAK
DELETE FROM #Primes
WHERE i % @num = 0
AND i > @num
END -- While
CREATE TABLE #Indexes (n INT PRIMARY KEY NOT NULL)
INSERT INTO #Indexes VALUES (2), (3), (4), (5), (6)
-- This is pretty simple. Run numbers where LEFT(prime,1..length) is prime, and then where RIGHT(prime,1..length) is prime.
-- Your answers are the ones that are in both lists.
; WITH TwoSided AS
(
SELECT p.i
FROM #Primes p
INNER JOIN #Indexes ndx
ON ndx.n <= LEN(p.i)
WHERE LEN(i) > 1 -- Problem wants 2 digits or more
AND LEFT(i,1) IN ('2', '3', '5', '7') -- We know the rightmost digit is prime
AND LEFT(i,n) IN (SELECT i FROM #Primes)
GROUP BY p.i
HAVING COUNT(*) = LEN(p.i) - 1
INTERSECT
SELECT p.i
FROM #Primes p
INNER JOIN #Indexes ndx
ON ndx.n <= LEN(p.i)
WHERE LEN(i) > 1 -- Problem wants 2 digits or more
AND RIGHT(i,1) IN ('2', '3', '5', '7') -- We know the leftmost digit is prime
AND RIGHT(i,n) IN (SELECT i FROM #Primes)
GROUP BY p.i
HAVING COUNT(*) = LEN(p.i) - 1
)
SELECT SUM(i)
FROM TwoSided
DROP TABLE #Primes
DROP TABLE #Indexes