T-SQL AND SQL SERVER TRICKS

Finding prime numbers with a Transact-SQL function

December 17, 2008 at 9:27 pm | Posted in TSQL Functions | Leave a comment

One of my first intensive experiences in coding (back in my Sinclair ZX81 days), was to write a piece of code which would determine if a number was a prime or not. Since my ZX81 was a very slow 8-bit machine, I had to code something that would work fast (and, of course, in FAST mode -read the Wiki, you’ll understand).

Writing a loop of dividers going from 2 to the (number – 1) and checking that the modulo equals 0 is programming 101, but what if your number has 6 digits?

The good thing is that you do need to loop to the number to test. A quick look at Wikipedia will explain why: you only need to loop from 2 to the square root of the number, or actually the floor or it, included.

Below is the function that I coded in SQL. I decided to not only use this “trick”, but to also create two parts in the same function:

1. Determine if the number to test is even
2. Only consider the odd numbers in the loop

Feel free to reuse, as long as you do not remove the comments.

SET ANSI_NULLS ON

GO

SET QUOTED_IDENTIFIER ON

GO

– =============================================

– Author:        Nicolas Verhaeghe

– Create date: 12/14/2008

– Description:   Determines if a given integer is a prime

/*

 

      SELECT dbo.IsPrime(1)

 

      SELECT dbo.IsPrime(9)

 

      SELECT dbo.IsPrime(7867)

 

*/

– =============================================

CREATE FUNCTION [dbo].[isPrime]

(

      @NumberToTest int

)

RETURNS bit

AS

BEGIN

      – Declare the return variable here

      DECLARE @IsPrime bit,

                  @Divider int

     

      – To speed things up, we will only attempt dividing by odd numbers

 

      – We first take care of all evens, except 2

      IF (@NumberToTest % 2 = 0 AND @NumberToTest > 2)

            SET @IsPrime = 0

      ELSE

            SET @IsPrime = 1 – By default, declare the number a prime

 

      – We then use a loop to attempt to disprove the number is a prime

     

      SET @Divider = 3 – Start with the first odd superior to 1

     

      – We loop up through the odds until the square root of the number to test

      – or until we disprove the number is a prime

      WHILE (@Divider <= floor(sqrt(@NumberToTest))) AND (@IsPrime = 1)

      BEGIN

 

            – Simply use a modulo

            IF @NumberToTest % @Divider = 0

                  SET @IsPrime = 0

            – We only consider odds, therefore the step is 2

            SET @Divider = @Divider + 2

      END  

 

      – Return the result of the function

      RETURN @IsPrime

 

END

 

Running the code below to find all the 78499 primes from 1 to 999999 takes 2’10 on a Pentium 4 2.6Ghz with 2GB of RAM running SQL Server 2005.

SET NOCOUNT ON

GO

 

CREATE TABLE #tmpPrimes(prime int)

 

DECLARE @TopNumber Int,

@CurrentNumber Int

 

SET @TopNumber = 999999

SET @CurrentNumber = 1

 

WHILE (@CurrentNumber <= @TopNumber)

BEGIN

 

      IF dbo.IsPrime(@CurrentNumber) = 1

            INSERT INTO #tmpPrimes

            SELECT @CurrentNumber

 

      SET @CurrentNumber = @CurrentNumber + 1

 

END