SQL Prime number function

You could, as you said, have a table that stores all the primes up to 10 million. Then it would be trivial to look up whether a number was prime or not. The question then is which method would be faster. I suspect the table would be much faster (I have not tested this claim).

Prime Table Solution

• https://www.simple-talk.com/sql/t-sql-programming/celkos-summer-sql-stumpers-prime-numbers/
  Provides a few solutions and there are more in the comments.

• https://sqlserverfast.com/blog/hugo/2006/09/the-prime-number-challenge-great-waste-of-time/
  Same here. A few solutions provided.

SQL Function Solutions

Solution 0

Here's one solution via Finding prime numbers with a Transact-SQL function:

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
–- =============================================
–- Author:        Nicolas Verhaeghe
–- Create date: 12/14/2008
–- Description:   Determines if a given integer is a prime
/*

      SELECT dbo.IsPrime(1)

      SELECT dbo.IsPrime(9)

      SELECT dbo.IsPrime(7867)

*/
–- =============================================
CREATE FUNCTION [dbo].[isPrime]
(
      @NumberToTest int
)
RETURNS bit
AS
BEGIN
      -– Declare the return variable here
      DECLARE @IsPrime bit,
                  @Divider int

      –- 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
      ELSE
            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)
      BEGIN

            –- Simply use a modulo
            IF @NumberToTest % @Divider = 0
                  SET @IsPrime = 0
            –- We only consider odds, therefore the step is 2
            SET @Divider = @Divider + 2
      END  

      –- Return the result of the function
      RETURN @IsPrime

END

Solution 1

Here's another solution via how to find whether is a prime or non prime with one select statement? There's more information in other comments as well.

CREATE FUNCTION isPrime
(
    @number INT
)
RETURNS VARCHAR(10)
BEGIN
    DECLARE @prime_or_notPrime INT
    DECLARE @counter INT
    DECLARE @retVal VARCHAR(10)
    SET @retVal = 'FALSE'

    SET @prime_or_notPrime = 1
    SET @counter = 2

    WHILE (@counter <= @number/2 )
    BEGIN

        IF (( @number % @counter) = 0 )
        BEGIN
            set @prime_or_notPrime = 0
            BREAK
        END

        IF (@prime_or_notPrime = 1 )
        BEGIN
            SET @retVal = 'TRUE'
        END

        SET @counter = @counter + 1
    END
    return @retVal
END

There is an interesting way to generate prime numbers without any function or iterative process (while) based on sequence generation. Basically a 2 .. @max sequence is generated and we pick all numbers that do no have other in the sequence that current%other = 0:

declare @max INT = 10000

;WITH all_numbers(n) AS
(
    SELECT 2
    UNION ALL
    SELECT n+1 FROM all_numbers WHERE n < @max
)
select all1.n as prime
from all_numbers all1
where not exists (select 1 from all_numbers all2 where all2.n < all1.n AND all1.n % all2.n = 0)
order by all1.n
-- beware, 0 means no limit. Otherwise 32767 can be the max specified
OPTION (MAXRECURSION 0)

The main drawback of this solution is performance (e.g. it took about 17s to generate all primes until 20000), but it is more SQLish since it does not rely on explicit iterative blocks (i.e. while)

I suspect this hasn't occurred to many people, but all you need to check is if each new number is divisible by previous primes...

create table prime (primeno bigint)
declare @counter bigint
set @counter = 2
while @counter < 1000000
begin
if not exists(select top 1 primeno from prime where @counter % primeno = 0 )

-- above, adding AND prime < @counter / 2 etc will reduce checking overheads further.

insert into prime select @counter
set @counter = @counter + 1
end
select * from prime order by 1

Lazy coding but even on a slow virtual pc like the one next to me you'll have everything up to a million in a few minutes. I make it 78,498 of them (if you don't count 1) unless I've overlooked something.

CREATE  proc prime  
@no int  
as   
declare @counter int  
set @counter =2  
begin  
while(@counter)<@no  
 begin  
 if(@no%@counter=0)  
  begin  
  select 'Not prime'  
  return  
  end  
  set @counter=@counter+1  
 end  
 select 'prime'  
 return  
end  

--exec prime 10