Post date: May 16, 2014 11:39:42 PM
"What is the 10001th prime number?"
Nothing much here. I already came up with a way to solve primes. The normal way will do and is plenty fast. The sieve of Eratosthenes is slower.
CREATE TABLE #Integers (i int not null primary key clustered)
INSERT INTO #Integers (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 #Integers o
CROSS JOIN #Integers d
CROSS JOIN #Integers h
CROSS JOIN #Integers k
CROSS JOIN #Integers k10
CROSS JOIN #Integers k100
)
INSERT INTO #Integers (i)
SELECT i
FROM Integers
WHERE i >= 10
-- Smaller divisors table
CREATE TABLE #Divisors (i int not null primary key clustered)
INSERT INTO #Divisors
SELECT i
FROM #Integers
WHERE i % 2 != 0
AND i > 2
AND i < SQRT(999999) + 1
;WITH NotPrimes(i) AS
(
-- Numbers divisible by 2 (other than 2)
SELECT i.i
FROM #Integers i
WHERE i.i > 2
AND i % 2 = 0
UNION
-- Numbers divisible by any number
SELECT i.i
FROM #Integers i
CROSS APPLY
(
SELECT 1 AS notprime
FROM #Divisors d
WHERE i.i % d.i = 0
AND d.i <= SQRT(i.i) + 1
) notprime
WHERE i.i > 2
),
Primes (i) AS
(
SELECT i
FROM #Integers
WHERE i >= 2
EXCEPT
SELECT i
FROM NotPrimes
WHERE i > 3
),
TenThousandAndOnePrimes(i) AS
(
SELECT TOP (10001) i
FROM Primes
ORDER BY 1
)
SELECT MAX(i)
FROM TenThousandAndOnePrimes
DROP TABLE #Integers
DROP TABLE #Divisors