Post date: Dec 31, 2014 1:31:36 AM
"Find the set of five primes with the lowest total sum where if you concatenate any two primes, in any order, the result is also prime."
I need a LOT of primes for this. And generating the list of primes takes the longest time. To solve this problem in a reasonable amount of time, I needed to speed up my Sieve of Eratosthenes. It still takes 6 minutes, but I need primes up to 100 million.
Of course, the fastest method is to simply have a table of primes sitting around for Euler problems.
CREATE TABLE #Integers (i bigint not null primary key)
INSERT INTO #Integers (i) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
CREATE TABLE #SmallIntegers (i bigint not null primary key)
-- The way to speed this up is to filter out primes that are divisible by small numbers at the start, before ever putting them into our sieve table.
-- Too big a list will hurt performance (that's the reason we use the sieve), but two few won't help enough. Performance seems best when #SmallIntegers is around 100 rows.
; WITH SmallIntegers (i) AS
(
SELECT (o.i + (10 * d.i)) * 2 + 1
FROM #Integers o
CROSS JOIN #Integers d
)
INSERT INTO #SmallIntegers
SELECT i
FROM SmallIntegers
WHERE i > 1
-- When generating the list of integers, don't write even numbers in the first place, and filter out any that are divisible by our table of 100 small numbers.
; WITH Integers(i) AS
(
SELECT (
o.i +
(10 * d.i) +
(100 * h.i) +
(1000 * k.i) +
(10000 * k10.i) +
(100000 * k100.i) +
(1000000 * m.i) +
(10000000 * m10.i)
) * 2 + 1
FROM #Integers o
CROSS JOIN #Integers d
CROSS JOIN #Integers h
CROSS JOIN #Integers k
CROSS JOIN #Integers k10
CROSS JOIN #Integers k100
CROSS JOIN #Integers m
CROSS JOIN #Integers m10
WHERE m10.i < 5
)
INSERT INTO #Integers (i)
SELECT i
FROM Integers i
WHERE i > 199
AND NOT EXISTS (SELECT 1
FROM #SmallIntegers si
WHERE i.i % si.i = 0)
-- We need to replace those the small numbers that weren't included in the above query.
INSERT INTO #Integers
SELECT i
FROM #SmallIntegers
WHERE i >= 10
DROP TABLE #SmallIntegers
-- Now Sieve it
DELETE FROM #Integers WHERE i < 2
DECLARE @max bigint
SELECT @max = MAX(i)
FROM #Integers
DECLARE @num bigint = 1
WHILE 1 = 1
BEGIN
SELECT @num = MIN(i)
FROM #Integers
WHERE i > @num
IF @num > SQRT(@max)
BREAK
DELETE FROM #Integers
WHERE i % @num = 0
AND i > @num
END
-- Take the table of primes and split them each into two primes, where each half is a prime.
-- This is a smaller table to work with. A relatively small number of primes can be made up of two concatenated primes.
-- Ignore those parts that would start with a zero.
; WITH PrimeCombos (i1, i2) AS
(
SELECT LEFT(i,1), SUBSTRING(RTRIM(i),2,10)
FROM #Integers
WHERE LEFT(i,1) IN (SELECT i FROM #Integers WHERE LEN(i) = 1)
AND SUBSTRING(RTRIM(i),2,10) IN (SELECT i FROM #Integers)
AND CONCAT(SUBSTRING(RTRIM(i),2,10),LEFT(i,1)) IN (SELECT i FROM #Integers)
UNION
SELECT LEFT(i,2), SUBSTRING(RTRIM(i),3,10)
FROM #Integers
WHERE LEFT(i,2) IN (SELECT i FROM #Integers WHERE LEN(i) = 2)
AND SUBSTRING(RTRIM(i),3,10) IN (SELECT i FROM #Integers)
AND CONCAT(SUBSTRING(RTRIM(i),3,10),LEFT(i,2)) IN (SELECT i FROM #Integers)
UNION
SELECT LEFT(i,3), SUBSTRING(RTRIM(i),4,10)
FROM #Integers
WHERE LEFT(i,3) IN (SELECT i FROM #Integers WHERE LEN(i) = 3)
AND SUBSTRING(RTRIM(i),4,10) IN (SELECT i FROM #Integers)
AND CONCAT(SUBSTRING(RTRIM(i),4,10),LEFT(i,3)) IN (SELECT i FROM #Integers)
UNION
SELECT LEFT(i,4), SUBSTRING(RTRIM(i),5,10)
FROM #Integers
WHERE LEFT(i,4) IN (SELECT i FROM #Integers WHERE LEN(i) = 4)
AND SUBSTRING(RTRIM(i),5,10) IN (SELECT i FROM #Integers)
AND CONCAT(SUBSTRING(RTRIM(i),5,10),LEFT(i,4)) IN (SELECT i FROM #Integers)
UNION
SELECT LEFT(i,5), SUBSTRING(RTRIM(i),6,10)
FROM #Integers
WHERE LEFT(i,5) IN (SELECT i FROM #Integers WHERE LEN(i) = 5)
AND SUBSTRING(RTRIM(i),6,10) IN (SELECT i FROM #Integers)
AND CONCAT(SUBSTRING(RTRIM(i),6,10),LEFT(i,5)) IN (SELECT i FROM #Integers)
UNION
SELECT LEFT(i,6), SUBSTRING(RTRIM(i),7,10)
FROM #Integers
WHERE LEFT(i,6) IN (SELECT i FROM #Integers WHERE LEN(i) = 6)
AND SUBSTRING(RTRIM(i),7,10) IN (SELECT i FROM #Integers)
AND CONCAT(SUBSTRING(RTRIM(i),7,10),LEFT(i,6)) IN (SELECT i FROM #Integers)
)
SELECT CONVERT(int,i1) AS i1, CONVERT(int,i2) AS i2
INTO #PrimeCombos
FROM PrimeCombos
WHERE i1 NOT LIKE '0%' AND i2 NOT LIKE '0%'
AND CONVERT(int,i1) < CONVERT(int,i2)
CREATE CLUSTERED INDEX IX_Combo ON #PrimeCombos (i1, i2)
DROP TABLE #Integers
--Now we have to take our table of prime combinations and find collections of 5 numbers that are all in PrimeCombos.
--Getting 3, 4, and 5 digit combinations is quite a pain. The basic process is joining PrimeCombos to itself 5 times, but this is a huge dataset.
--We have to test number 1 and number 3, #2 and #3, #1 and #4, #2 and #4, #3 and #4, #1 and #5, #2 and #5, #3 and #5, and #4 and #5. They ALL must be in PrimeCombos.
--To do this, I will do join 3 numbers, put it into a table. Then go to number 4, into a table. Then 5.
SELECT pc1.i1, pc1.i2, pc2.i2 AS i3
INTO #Combo3
FROM #PrimeCombos pc1
INNER JOIN #PrimeCombos pc2
ON pc2.i1 = pc1.i1
AND pc2.i2 <> pc1.i2
WHERE EXISTS (SELECT 1
FROM #PrimeCombos pcsub
WHERE pcsub.i1 = pc1.i1
AND pcsub.i2 = pc2.i2)
AND EXISTS (SELECT 1
FROM #PrimeCombos pcsub
WHERE pcsub.i1 = pc1.i2
AND pcsub.i2 = pc2.i2)
SELECT c.*, pc2.i2 AS i4
INTO #Combo4
FROM #Combo3 c
INNER JOIN #PrimeCombos pc2
ON pc2.i1 = c.i1
AND pc2.i2 <> c.i2
AND pc2.i2 <> c.i3
WHERE EXISTS (SELECT 1
FROM #PrimeCombos pcsub
WHERE pcsub.i1 = c.i1
AND pcsub.i2 = pc2.i2)
AND EXISTS (SELECT 1
FROM #PrimeCombos pcsub
WHERE pcsub.i1 = c.i2
AND pcsub.i2 = pc2.i2)
AND EXISTS (SELECT 1
FROM #PrimeCombos pcsub
WHERE pcsub.i1 = c.i3
AND pcsub.i2 = pc2.i2)
-- Final join, so take the one with the smallest sum. Return the sum.
SELECT TOP 1 c.i1 + c.i2 + c.i3 + c.i4 + pc2.i2
FROM #Combo4 c
INNER JOIN #PrimeCombos pc2
ON pc2.i1 = c.i1
AND pc2.i2 <> c.i2
AND pc2.i2 <> c.i3
AND pc2.i2 <> c.i4
WHERE EXISTS (SELECT 1
FROM #PrimeCombos pcsub
WHERE pcsub.i1 = c.i1
AND pcsub.i2 = pc2.i2)
AND EXISTS (SELECT 1
FROM #PrimeCombos pcsub
WHERE pcsub.i1 = c.i2
AND pcsub.i2 = pc2.i2)
AND EXISTS (SELECT 1
FROM #PrimeCombos pcsub
WHERE pcsub.i1 = c.i3
AND pcsub.i2 = pc2.i2)
AND EXISTS (SELECT 1
FROM #PrimeCombos pcsub
WHERE pcsub.i1 = c.i4
AND pcsub.i2 = pc2.i2)
ORDER BY c.i1 + c.i2 + c.i3 + c.i4 + pc2.i2
DROP TABLE #PrimeCombos