USE PrimeNumberTest
GO
-- log a status message
SELECT GETDATE() AS [Starting..]
SET NOCOUNT ON
GO
-- remove the three tables we're going to use
-- if they're present from a previous run
IF EXISTS (SELECT 1 FROM sys.objects WHERE name = 'SetBuilderDecimal')
DROP TABLE SetBuilderDecimal
GO
IF EXISTS (SELECT 1 FROM sys.objects WHERE name = 'Candidate')
DROP TABLE Candidate
GO
IF EXISTS (SELECT 1 FROM sys.objects WHERE NAME = 'ComparisonMatrix')
DROP TABLE ComparisonMatrix
GO
-- create the table to hold the set of values between 1 and 1M
CREATE TABLE SetBuilderDecimal (
Id DECIMAL(12,2) PRIMARY KEY
)
go
-- create the table to hold the set of values to test from primacy
-- (we are going to remove some low-hanging fruit for performance reasons,
-- so we need a distinct table for this purpose)
CREATE TABLE Candidate (
CandidateValue DECIMAL(12,2)
)
GO
-- create the table where the calculations will be performed
-- Base is the number we're testing for primacy
-- Factor is the number we're dividing it by
-- Quotient is the result of the division
-- IsQuotientInteger is a bit flag indicating whether the Quotient is an integer
CREATE TABLE ComparisonMatrix (
Base DECIMAL(12,2),
Factor DECIMAL(12,2),
Quotient AS Base/Factor,
IsQuotientInteger AS CASE
WHEN Base/Factor = CAST(Base/Factor AS int) THEN CAST(1 AS int)
ELSE CAST(0 AS int)
END PERSISTED
)
-- build indexes on the ComparisonMatrix table to improve perfomance
CREATE UNIQUE CLUSTERED INDEX ComparisonMatrix_PK ON ComparisonMatrix(Base, Factor)
CREATE INDEX ComparisonMatrix_ID1 ON ComparisonMatrix(IsQuotientInteger)
GO
-- build an INSTEAD OF INSERT trigger so we only save the integer factors
-- THIS IS PURELY A PERFORMANCE ISSUE;
-- as discussed below
-- this syntax is new in SQL Server 2005; the BOL reference may be found here:
-- ms-help://MS.SQLCC.v9/MS.SQLSVR.v9.en/udb9/html/0001f651-fcfa-401b-baf2-0ec6b1671116.htm
--
-- A BRIEF DISCUSSION:
-- what we're doing here is tuning our INSERT statement for the table CompressionMatrix below to ignore
-- the transactions which do not result in an integer quotient. This will make the commiting of
-- these INSERT transactions orders of magnitude faster, since only a small fraction of the volume
-- will result in integer quotients
CREATE TRIGGER IOI_ComparisonMatrix
ON ComparisonMatrix
INSTEAD OF INSERT
AS
INSERT ComparisonMatrix (
Base,
Factor
)
SELECT Base,
Factor
FROM inserted
WHERE IsQuotientInteger = 1
GO
-- log a status message
SELECT GETDATE() AS [Tables Created..]
GO
-- using Shaun's syntax (because it doesn't have a database footprint),
-- populate SetBuilder
;WITH digits(i) AS (
SELECT 1.0 AS I UNION ALL SELECT 2.0 UNION ALL SELECT 3.0 UNION ALL
SELECT 4.0 UNION ALL SELECT 5.0 UNION ALL SELECT 6.0 UNION ALL
SELECT 7.0 UNION ALL SELECT 8.0 UNION ALL SELECT 9.0 UNION ALL
SELECT 0.0
),
-- generate 1M rows each with a unique row number, i
sequence(i) AS (
SELECT d1.i + (10*d2.i) + (100*d3.i) + (1000*d4.i) + (10000*d5.i) + (100000*d6.i)
FROM digits AS d1,
digits AS d2,
digits AS d3,
digits AS d4,
digits AS d5,
digits AS d6
)
INSERT SetBuilderDecimal (Id)
SELECT i+1 -- CTE gives us 0-999999; we want 1-1000000
FROM sequence
-- populate Candidate
INSERT Candidate (CandidateValue)
SELECT Id
FROM SetBuilderDecimal
GO
-- now delete the low-hanging fruit from Candidate
-- WE ARE ONLY DONG THIS FOR PERFORMANCE; the algorhytm can handle them
-- NOTE that these fifteen DELETE statements, which encompass the first 15 prime numbers and
-- thier multiples, removes of the candidate values
DELETE Candidate WHERE CandidateValue/2 = CAST(CandidateValue/2 AS int) AND CandidateValue > 2
DELETE Candidate WHERE CandidateValue/3 = CAST(CandidateValue/3 AS int) AND CandidateValue > 3
DELETE Candidate WHERE CandidateValue/5 = CAST(CandidateValue/5 AS int) AND CandidateValue > 5
DELETE Candidate WHERE CandidateValue/7 = CAST(CandidateValue/7 AS int) AND CandidateValue > 7
DELETE Candidate WHERE CandidateValue/11 = CAST(CandidateValue/11 AS int) AND CandidateValue > 11
DELETE Candidate WHERE CandidateValue/13 = CAST(CandidateValue/13 AS int) AND CandidateValue > 13
DELETE Candidate WHERE CandidateValue/17 = CAST(CandidateValue/17 AS int) AND CandidateValue > 17
DELETE Candidate WHERE CandidateValue/19 = CAST(CandidateValue/19 AS int) AND CandidateValue > 19
DELETE Candidate WHERE CandidateValue/23 = CAST(CandidateValue/23 AS int) AND CandidateValue > 23
DELETE Candidate WHERE CandidateValue/29 = CAST(CandidateValue/29 AS int) AND CandidateValue > 29
DELETE Candidate WHERE CandidateValue/31 = CAST(CandidateValue/31 AS int) AND CandidateValue > 31
DELETE Candidate WHERE CandidateValue/37 = CAST(CandidateValue/37 AS int) AND CandidateValue > 37
DELETE Candidate WHERE CandidateValue/41 = CAST(CandidateValue/41 AS int) AND CandidateValue > 41
DELETE Candidate WHERE CandidateValue/43 = CAST(CandidateValue/43 AS int) AND CandidateValue > 43
DELETE Candidate WHERE CandidateValue/47 = CAST(CandidateValue/47 AS int) AND CandidateValue > 47
-- uncomment this SELECT statement to confirm that we have cut 1M candidates down to 138,760
-- SELECT COUNT(*) FROM Candidate
GO
-- log a status message
SELECT GETDATE() AS [Tables Populated..]
GO
-- keep some house for what comes..
DECLARE @CandidateValue DECIMAL(12,2),
@Counter DECIMAL (12,2),
@IntCandidateValue INT
-- initalize a counter
SET @Counter = 1
-- declare a cursor to traverse the Candidate table
DECLARE TraverseCandidateTable CURSOR FAST_FORWARD READ_ONLY FOR
SELECT CandidateValue,
CAST(CandidateValue AS INT)
FROM Candidate
ORDER BY CandidateValue
-- open the cursor and get the first record
OPEN TraverseCandidateTable
FETCH NEXT
FROM TraverseCandidateTable
INTO @CandidateValue,
@IntCandidateValue
-- log a status message
SELECT GETDATE() AS [Cursor Loop Starts..]
-- open a transaction
-- (careful transaction control is necessary to avoid rampant growth of the transaction logs)
BEGIN TRAN
-- start a loop which will run as long as the cursor finds a record
WHILE @@FETCH_STATUS = 0
BEGIN
-- insert the full range of possible factors for the candidate value
-- into the comparison matrix
-- (use the SetBuilderDecimal table to aid this work)
INSERT ComparisonMatrix (
Base,
Factor
)
SELECT @CandidateValue,
Id
FROM SetBuilderDecimal
WHERE Id <= @CandidateValue
-- log a database commit anf start a new transaction
-- if it's been 200 transactions since we did so
IF @Counter/200.0 = CAST(@Counter/200 AS int)
BEGIN
COMMIT TRAN
CHECKPOINT
-- log a status message if it's been 1000 transactions since we did so
IF @Counter/1000.0 = CAST(@Counter/1000 AS int)
SELECT GETDATE() AS [One Thousand More..], @Counter AS [Current Count..], @CandidateValue AS [Current Candidate..]
BEGIN TRAN
END
-- get the next candidate value
FETCH NEXT
FROM TraverseCandidateTable
INTO @CandidateValue,
@IntCandidateValue
-- increment the final transaction
SET @Counter = @Counter + 1
END
-- we're out of the loop;
-- we still need to commit the final transaction
COMMIT TRAN
-- clost and deallocate the cursor
CLOSE TraverseCandidateTable
DEALLOCATE TraverseCandidateTable
-- log a status message
SELECT GETDATE() AS [Cursor Loop Complete..]
-- generate the list of prime numbers
-- if the SUM(IsQuotientInteger)=2 (where IsQuotientInteger=1 when a particular member of the set
-- is a precise integer factor of the candidate value), then that candidate is a prime number,
-- because IsQuotientInteger will equal 1 for 1 and the candidate itself.