## Finding prime numbers with a Transact-SQL function

December 17, 2008 at 9:27 pm | Posted in TSQL Functions | Leave a commentOne 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

Blog at WordPress.com.

Entries and comments feeds.