SQL Prime number function

Question

If I have a number X and want to say IsPrime(X) = true/false using sql-server what is the best approach?

Do I just import a table of primes or is there an algorithm that is fairly efficient for the smaller primes?

Note: I'm not interested in numbers greater than approx. 10 million.

Ended up using the following:

CREATE FUNCTION [dbo].[isPrime]
(
    @number INT
)
RETURNS VARCHAR(10)

BEGIN


    DECLARE @retVal VARCHAR(10) = 'TRUE';

    DECLARE @x INT = 1;
    DECLARE @y INT = 0;

    WHILE (@x <= @number )
    BEGIN

            IF (( @number % @x) = 0 )
            BEGIN
                SET @y = @y + 1;
            END

            IF (@y > 2 )
            BEGIN
                SET @retVal = 'FALSE'
                BREAK
            END

            SET @x = @x + 1

    END

    RETURN @retVal
END

Answer 1

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

Answer 2

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.

Answer 3

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)

Answer 4

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  

Answer 5

Here's a simple script that works nicely. Adjust @num as needed:

declare @nonprimes table (number int) 
declare @primes table (number int) 
declare @num int = 2
declare @divisor int  = 1
while @num<10000
begin

while @divisor>1
begin
if @num % @divisor=0 
insert @nonprimes
select @num
if @@rowcount>0 goto A

set @divisor=@divisor-1

end
insert @primes
select @num
A: set @num=@num+1 
set @divisor=@num-1

end

select sum(number) from @primes

Answer 6

How about this (Tested on PostgreSQL):

SELECT Listagg (num, ',') 
         within GROUP (ORDER BY num) 
FROM   (SELECT n1.num   num, 
               SUM(CASE 
                     WHEN MOD(n1.num, n2.num) = 0 THEN 1 
                     ELSE 0 
                   END) AS cnt 
        FROM   (SELECT ROWNUM num 
                FROM   dual 
                CONNECT BY LEVEL <= 1000) n1, 
               (SELECT ROWNUM num 
                FROM   dual 
                CONNECT BY LEVEL <= 1000) n2 
        WHERE  n1.num <> 1 
               AND n2.num <> 1 
               AND n1.num >= n2.num 
        GROUP  BY n1.num) a 
WHERE  cnt = 1; 

Answer 7

declare @max INT = 50000
declare @all_numbers table (n int not null primary key, squareRoot decimal(10,1))
;WITH all_odds(n) AS
(
    SELECT 3
    UNION ALL
    SELECT n+2 FROM all_odds WHERE n+2 < @max
)
    INSERT INTO @all_numbers
    SELECT 2 as n, SQRT(2)
    UNION ALL
    SELECT n, SQRT(n) FROM all_odds
    OPTION (MAXRECURSION 0)

select all1.n as prime
from @all_numbers all1
where not exists (select 1 from @all_numbers all2 where all2.n <= all1.squareRoot AND all1.n % all2.n = 0)
order by all1.n

This takes under a sec for 50k

Answer 8

Here's a combination of number generation and checking for prime numbers.

This is a quick running prime number checker.

The generator will create a list of numbers up to 10,000.
The @CheckNumber can be set to any value that is needed.

Feel free to scale up the max generated number to meet your needs.

DECLARE @CheckNumber INT;
SET @CheckNumber = 29;

with data as (
    SELECT (ones.n + 10*tens.n + 100*hundreds.n + 1000*thousands.n ) + 1 as number
FROM (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) ones(n),
     (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) tens(n),
     (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) hundreds(n),
     (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) thousands(n)
)

select sub1.number1
from (
  select distinct d1.number as number1, d2.number as number2
  from data as d1 
  cross join data as d2
  where d1.number % d2.number != 0
) as sub1
group by sub1.number1
having count(sub1.number2) = max(sub1.number2)-2
and sub1.number1 = @CheckNumber
order by sub1.number1

Answer 9

Create PROC prime @num int , @flag int OUTPUT
AS
   Declare @i=50
   set

   while (@i<@num)
Begin
     if @i%@num=0
     break
set
     @i=@i+1
  End
  if @i=@num
 set
    @glag=1
else
   set
      @flag=2


Declare @ans int
Exec prime 50,@flag=@ans OUTPUT
if @ans=1
print 'The number is prime'
else
print 'The number is composite'