💎SQL Reloaded: Prime Numbers

I was just thinking about prime numbers and why people had such a fascination about them. In mysticism every number has a powerful meaning, a power coming from inside, and therewith attracts certain powers from exterior, is strange, hard to understand all this, especially how all numbers can be reduced to a number between 1 and 9.  Every philosophy has a little truth in it. 

 
I was trying to find a nice article on number reduction, for example the one from sourceryforge could be useful. Last week I implemented a function which returns the reduction of any sequence, could be date or number. I was intending to apply it on prime numbers, but even if can be observed certain similarities between different chains, is difficult to believe this will lead anywhere. 

 CREATE FUNCTION dbo.NumberReduction( @text varchar(50)) RETURNS smallint /* Purpose: reduces to number a sequence of digits Parameters: @text varchar(50) - digits sequence 

 Notes: the function works with any sequnce of alphanumeric, not numeric values being ignored Sample: 

SELECT dbo.NumberReduction('11/17/2005') 

SELECT dbo.NumberReduction('1234') 

SELECT dbo.NumberReduction('1234 8993 90003 3456') */ 

 BEGIN    

DECLARE @index smallint    

DECLARE @total int    

SET @index = 1    

SET @total = 0    --for each char in alphanumeric sequence    

WHILE (@index<=len(@text))   

 BEGIN          

IF IsNumeric(Substring(@text, @index, 1)) = 1         

SET @total = @total + Cast(Substring(@text, @index, 1) as smallint)       

SET @index = @index+1    

END    

--if the number is not in 1..9 range, it calls further the NumberReduction for the new total    

IF len(@total)>1       

SET @total = dbo.NumberReduction(@total)    

RETURN @total END 

I tried to generate the prime numbers between 1 and 1000000 to analyze how many prime numbers are for each thousand. 

SELECT PrimeNumber/1000 DataSet , count(*) NumberPrimeNumbers 

FROM PrimeNUmbers 

GROUP BY PrimeNumber/1000 ORDER BY DataSet 

As it seems the maximum number of prime numbers is reached for the first thousand and decreases. DataSet*1000 

 Number Prime Numbers -------------------- ------------------ 0 (2..1000) 168 1 (1001..2000) 135 2 (2001..3000) 127 3 ........... 120 4 ........... 119 5 ........... 114 6 ........... 117 7 ........... 107 8 ........... 110 9 ........... 112 10 .......... 106 11 .......... 103 12 .......... 109 13 .......... 105 14 .......... 102 15 .......... 108 16 .......... 98 17 .......... 104 18 .......... 94 19 .......... 104 20 .......... 98 ........................... 980 ......... 67 981 ......... 75 982 ......... 70 983 ......... 70 984 ......... 70 985 ......... 76 986 ......... 76 987 ......... 63 988 ......... 71 989 ......... 72 990 ......... 71 991 ......... 79 992 ......... 65 993 ......... 68 994 ......... 78 995 ......... 69 996 ......... 69 997 ......... 83 998 ......... 74 999 ......... 65 

💎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!