SQL Reloaded: To be or not to be a Prime

   According to Wolfram a prime number is "any positive integer p>1 that has no positive integer divisors other than 1 and p itself. In other words there is no positive integer numbers p>m>1 that p = m*n, n>1. So, to check whether p is prime all we have to do is to check if any number m between 2 and p-1 is not a divisor for p.    

   If m is not a divisor for p then we could write: p/m = n + r, r> 0, this is in mathematics, but in programming even if is SQL, C++ or any programming language, when working with integers, by p/m is understood n while by p mod m is r.

   Respecting the order of operations (p/m)*m = p only if m is a divisor for p. Now, is it really necessary to check all the numbers between 2 and p-1 if they are or not divisors for p? Probably not, when m increases, p/m decreases, and also the range of possible divisors, which is between m+1 and p/m-1 until m becomes greater or equal with p/m. m=p/m only when m is the square from p, so is necessary and sufficient to check only the values between 2 and √p.    

    To summarize, if all the numbers m betwen 2 and √p are not divisors of p then p is prime. This is the test approach used in IsPrime function:

CREATE FUNCTION dbo.IsPrime(
 @number bigint)
RETURNS smallint
/*
   Purpose: checks if a positive integer is prime number
   Parameters: @number bigint - the number to be checked if prime
   Notes: 
   Sample: SELECT dbo.IsPrime(1000)
  SELECT dbo.IsPrime(947)
  SELECT dbo.IsPrime(111913)
  SELECT dbo.IsPrime(113083)
*/
BEGIN
    DECLARE @index bigint
 DECLARE @result bit

 SET @index = 2
    SET @result = 1

 WHILE (@index<=sqrt(@number))
 BEGIN
  IF (@number = (@number/@index)*@index)
   SET @result = 0 

  SET @index = @index+1
 END

 RETURN @result
END

The pListPrimeNumbers will be used to test the function:

CREATE PROCEDURE dbo.pListPrimeNumbers(
  @startInterval bigint
, @endInterval bigint)
AS
/*
   Purpose: lists the prime numbers from a the [@startInterval, @endInterval] interval 
   Parameters: @startInterval bigint - the left side of the interval in which will be searched the prime numbers
      @endInterval bigint - the right side of the interval in which will be searched the prime numbers
   Notes: 
   Sample: EXEC dbo.pListPrimeNumbers 900, 1000
           EXEC dbo.pListPrimeNumbers 111900, 112900
*/
DECLARE @index bigint
SET @index = @startInterval

--for each integer in interval
WHILE (@index<=@endInterval)
BEGIN  
    -- list a number if prime 
 IF (dbo.IsPrime(@index)=1)
  SELECT @index [Prime Numbers]

 SET @index = @index+1 
END

 
   One can use a simple table to store the results, which will allow further analyssis of the data:

-- creating the table 
CREATE TABLE PrimeNumbers (PrimeNumber bigint)

-- inserting the data 
INSERT PrimeNumbers
EXEC dbo.pListPrimeNumbers 1, 10000

Notes:    
The utility of IsPrime function is relative, primarily because there are not many the cases when such a function is needed in SQL, and secondarily because the performance gets poorer with the number tested. Programming languages like VB.Net or C# are more appropriate for such tasks. Initially I wanted to test the performance of implementing IsPrime in SQL vs implementing it as a managed function, but an error stopped me from the attempt:
Msg 6505, Level 16, State 1, Procedure IsPrimeNumber, Line 1 Could not find Type 'UserDefinedFunctions' in assembly 'MyLibrary'.    

3 months ago the same piece of code worked without problems, but since then I had to reinstall the SQL Server because I couln't use DTS packages after I installed LINQ preview. Welcome to the "real" world of Microsoft :(.

Happy Coding!