TSQL program to find the largest prime number

Question

I have a table of integers as

number
--------
104723
104729
9998
448

Objective is to find the largest prime among a collection of numbers. I have done so with the below program

Declare @t table(number int)
Insert into @t values(104723),(104729),(9998),(448)

Declare @maxNum INT
SELECT @maxNum = MAX(number) FROM @t

--generate a number table from 2 to the maximum number supplied
;WITH Cte AS (
    SELECT 2 AS num 
        UNION ALL
    SELECT num+1 
    FROM cte 
    WHERE num<@maxNum)

SELECT TOP(1) num AS 'Largest Prime' FROM cte
--filter by some known prime numbers (keeping the range between 2 to 19
WHERE 
    (num=2 OR num%2!=0) AND
    (num=3 OR num%3!=0) AND
    (num=5 OR num%5!=0) AND
    (num=7 OR num%7!=0) AND
    (num=11 OR num%11!=0) AND
    (num=13 OR num%13!=0) AND
    (num=17 OR num%17!=0) AND
    (num=19 OR num%19!=0) 
ORDER BY 1 DESC
OPTION (MAXRECURSION 0)


/*
Largest Prime
-------------
104729
*/

But I am sure there will be much more better way to do so. How can I optimize the same?

T-SQL is a scripting language and the wrong choice for this problem. — Gordon Linoff, Oct 03 '16 at 12:54
You can use the SQL `isPrime` function defined here [SQL Prime number function](http://stackoverflow.com/questions/15566619/sql-prime-number-function) — P.Bra, Oct 03 '16 at 13:00
This script doesn't find the largest prime. It finds the largest number less than or equal to the largest number in the table that is not divisible by the first 8 primes. Notably, it a) can return a value that never appeared in the original table and b) doesn't do a very complete job of assessing primality. — Damien_The_Unbeliever, Oct 03 '16 at 13:55

gofr1 · Accepted Answer · 2016-10-03T14:33:21.623

I modified a little bit your query:

DECLARE @t TABLE (number int)
INSERT INTO @t VALUES
(104723),(104729),(9998),(448)

DECLARE @maxNum int
SELECT @maxNum = MAX(number) 
FROM @t

;WITH cte AS (
    SELECT 2 AS num 
    UNION ALL
    SELECT num+1 
    FROM cte 
    WHERE num < @maxNum
)

SELECT MAX(number) as LargestPrime
FROM (
    SELECT number
    FROM @t t
    CROSS JOIN Cte c
    WHERE t.number%c.num=0 
    GROUP BY number
    HAVING COUNT(num) = 1
) as t
OPTION (MAXRECURSION 0)

This will bring largest prime number from @t table:

LargestPrime
104729

The main idea is to get largest number, build CTE with numbers from 2 to max. Then do a Cartesian join, so we can try to get modulo of each number from @t and CTE. If there are numbers which have modulo > 0 more than 1 time - they are not prime.

LukStorms · Answer 2 · 2016-10-06T13:56:51.030

A slightly different approach.

By filling a table with only prime numbers.

Then simply join the table on the primes and return the max.

declare @T table (number int primary key);
insert into @T values (104723),(104729),(9998),(448);

declare @maxNum int;
set @maxNum = (select max(number) from @T);

declare @primes TABLE (n int primary key);
insert into @primes (n) values (2);

with cte as (
  SELECT 3 AS n 
  UNION ALL
  SELECT n+2 FROM cte WHERE n+2 <= @maxNum) -- Only uneven numbers lower then @maxNum
insert into @primes (n)
select n from cte
where (n%3 > 0 and n%5 > 0 and n%7 > 0) or n < 8  -- Filter a majority of the non-primes
option (MAXRECURSION 0);

-- Remove the numbers where the modulus by a lower number returns 0
-- Limiting it to the numbers lower or equal to the square root of the number.
-- The idea behind this is that even if the number has a divisor that's higher than the square root, it would mean there also exists a lower divisor.
DELETE p FROM @primes p
WHERE EXISTS (
  SELECT 1 FROM @primes AS p1
  WHERE p1.n <= CEILING(SQRT(p.n)) and (p.n%p1.n) = 0 and p.n > 8
);  


select max(t.number) as LargestPrime 
from @T t 
inner join @primes p on (t.number = p.n);

Of course, if you do this often, then it might be worth it to create a permanent table with a lot of prime numbers.

TSQL program to find the largest prime number

2 Answers2