Post date: Dec 17, 2014 2:19:57 AM
"If you start with 1 in the center, 2 to the right of it, 3 above the 2, 4 to the left of the 3, and so on, building a square of numbers using a counterclockwise spiral, what is the minimum side length (above 1) where less than 10% of the numbers along both diagonals are prime?"
It is easy to join to a table of primes, but if you don't have a table with primes up to hundreds of millions available, it takes a LONG time to build one. And we don't know, going in, how long we will need to go. So quick prime calculation methods, which depend on an array (table in this case) of primes will not be quick and will take a huge amount of space. So in this case, it's a lot faster to use the inefficient IsPrime function, because we only need to check the numbers along the diagonals. This is a much tinier amount, so inefficient or not, it's the better solution.
CREATE FUNCTION dbo.IsPrimeNumber (@number int)
RETURNS bit
AS
BEGIN
IF @number < 2
RETURN 0
DECLARE @counter int = 3
IF @number = 2
RETURN 1
IF @number % 2 = 0
RETURN 0
WHILE @counter <= SQRT(@number)
BEGIN
IF @number % @counter = 0
RETURN 0
SET @counter = @counter + 2
END -- While
RETURN 1
END
GO
CREATE TABLE #Integers (i INT NOT NULL PRIMARY KEY)
-- Start with a fairly large table of integers to use as the background for our diagonal calculations.
-- This gives a speed bonus over simply incrementing a variable, though of course I had to try it several times with bigger numbers until I got a non-null answer.
; WITH Integers (i) AS
(
SELECT 1
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 14000
)
INSERT INTO #Integers
SELECT i
FROM Integers
OPTION (MAXRECURSION 20000)
-- Build a dataset with only the diagonals and a counter to help us calculate how far from the center horizontally/vertically each number is.
-- As each number comes out of the query, the running totals tell us how many numbers there are in the diagonals and how many so far are prime.
; WITH Progression (i) AS
(
SELECT 8 * i
FROM #Integers
),
UR (i) AS
(
SELECT 3
UNION ALL
SELECT i + 2
FROM Progression
),
DR (i) AS
(
SELECT 1
UNION ALL
SELECT i
FROM Progression
),
DL (i) AS
(
SELECT 1
UNION ALL
SELECT i - 2
FROM Progression
),
UL (i) AS
(
SELECT 1
UNION ALL
SELECT i - 4
FROM Progression
),
Nums (i, j) AS
(
SELECT SUM(i) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
, ROW_NUMBER() OVER (ORDER BY i) + 1
FROM UR
UNION
SELECT SUM(i) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
, ROW_NUMBER() OVER (ORDER BY i)
FROM DR
UNION
SELECT SUM(i) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
, ROW_NUMBER() OVER (ORDER BY i)
FROM DL
UNION
SELECT SUM(i) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
, ROW_NUMBER() OVER (ORDER BY i)
FROM UL
),
SideLengthGroups AS
(
SELECT j * 2 - 1 AS SideLength
, COUNT(*) AS Numbers
, SUM(CONVERT(tinyint,dbo.IsPrimeNumber(n.i))) AS Primes
FROM Nums n
GROUP BY j
),
RunningTotals AS
(
SELECT SideLength
, SUM(Numbers) OVER (PARTITION BY 1 ORDER BY SideLength ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS Numbers
, SUM(Primes) OVER (PARTITION BY 1 ORDER BY SideLength ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS Primes
FROM SideLengthGroups
)
SELECT MIN(SideLength)
FROM RunningTotals
WHERE SideLength > 1
AND 1.0 * Primes/Numbers < 0.10
DROP TABLE #Integers
GO
DROP FUNCTION dbo.IsPrimeNumber
GO