💎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. It's strange and probably hard to understand the reduction of numbers between 1 and 9. Probably, each 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 it can be observed certain similarities between different chains, it's 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: 
*/ 
BEGIN    
	DECLARE @index smallint = 1 
	DECLARE @total int = 0 

	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 

-- testing the function
SELECT dbo.NumberReduction('11/17/2005') 
SELECT dbo.NumberReduction('1234') 
SELECT dbo.NumberReduction('1234 8993 90003 3456') 

Now, let's look at the number of 9592 primes found in the first 100.000 numbers:

-- number of primes in each thousands numbers 
SELECT PrimeNumber/1000+1 DataSet 
, count(*) NumberPrimeNumbers 
FROM PrimeNumbers 
GROUP BY PrimeNumber/1000+1
ORDER BY DataSet 

As it seems the maximum number of prime numbers is reached for the first thousand and decreases until is stabilizes somehow. It's more interesting what happens when the numbers are really big, however special techniques are used for testing such big numbers. The record is currently held by 2^136,279,841-1 with 41,024,320 digits (see Wikipedia). There are also interesting visualizations on prime numbers: see Ulam's spiral.

Here's a chart with the number of prime numbers and the table generated from the above script:

Thousands	Number Primes
1	169
2	135
3	127
4	120
5	119
6	114
7	117
8	107
9	110
10	112
11	106
12	103
13	109
14	105
15	102
16	108
17	98
18	104
19	94
20	104
21	98
22	104
23	100
24	104
25	94
26	98
27	101
28	94
29	98
30	92
31	95
32	92
33	106
34	100
35	94
36	92
37	99
38	94
39	90
40	96
41	88
42	101
43	102
44	85
45	96
46	86
47	90
48	95
49	89
50	98
51	89
52	97
53	89
54	92
55	90
56	93
57	99
58	91
59	90
60	94
61	88
62	87
63	88
64	93
65	80
66	98
67	84
68	99
69	80
70	81
71	98
72	95
73	90
74	83
75	92
76	91
77	83
78	95
79	84
80	91
81	88
82	92
83	89
84	84
85	87
86	85
87	88
88	93
89	76
90	94
91	89
92	85
93	97
94	86
95	87
96	95
97	84
98	82
99	87
100	87

See also plotting with prime numbers.

Happy coding!

💎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:    
1) 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'."  

About 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 :(.
2) The code has been tested successfully also on a SQL database in Microsoft Fabric.

Happy Coding!