17 November 2005
To be or not to be... prime
First of all, what is a prime number? According to Wolfram a prime number is "any positive integer p>1 that has no positive integer divisors other than 1 and p itself. Not bad, in other words there is no positive integer numbers p>m>1 that p = m*n, n>1. So, 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. Complicated? maybe at the first sight if somebody is not used with mathematics. To summarize, if all the numbers m betwen 2 and √p are not divisors of p then p is prime. This is the "theory" 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 function is ready, could be useful a piece of code to test the function for a certain interval. This is what pListPrimeNumbers is supposed to do. 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 The only problem with the stored procedure is that when its results are listed in grid and it returns more than 100 prime numbers will get receive the message: The query has exceeded the maximum number of result sets that can be displayed in the results grid. Only the first 100 result sets are displayed in the grid. Cool message, isn't it? Happens, but no problem appears if the results are displayed to text or file: Prime Numbers -------------------- 907 (1 row(s) affected) Prime Numbers -------------------- 911 (1 row(s) affected) Prime Numbers -------------------- 919 Still, the result is not what has been expected. Using a DTS Package will not bring the wanted result because it will return only the first record. It's easier to create a simple table, which will allow further analyssis of the data. CREATE TABLE PrimeNumbers (PrimeNumber bigint) and insert in it the results returned by pListPrimeNumbers stored procedure INSERT PrimeNumbers EXEC dbo.pListPrimeNumbers 1, 10000 Note: The utility of IsPrime function is doubtful, there are not many the cases when such a function is needed in SQL. Initially I wanted to test the performance of implementing IsPrime in SQL vs implementing it as a managed function, but another surprize: Msg 6505, Level 16, State 1, Procedure IsPrimeNumber, Line 1 Could not find Type 'UserDefinedFunctions' in assembly 'MyLibrary'. And what's even more interesting is that 3 months ago the same functionality 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 :(.