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?
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments