One 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
SET QUOTED_IDENTIFIER ON
— Author: Nicolas Verhaeghe
— Create date: 12/14/2008
— Description: Determines if a given integer is a prime
CREATE FUNCTION [dbo].[isPrime]
— Declare the return variable here
DECLARE @IsPrime bit,
— 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
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)
— Simply use a modulo
IF @NumberToTest % @Divider = 0
SET @IsPrime = 0
— We only consider odds, therefore the step is 2
SET @Divider = @Divider + 2
— Return the result of the function
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
CREATE TABLE #tmpPrimes(prime int)
DECLARE @TopNumber Int,
SET @TopNumber = 999999
SET @CurrentNumber = 1
WHILE (@CurrentNumber <= @TopNumber)
IF dbo.IsPrime(@CurrentNumber) = 1
INSERT INTO #tmpPrimes
SET @CurrentNumber = @CurrentNumber + 1