## SQL and the search for Prime and Perfect numbers

After a bit of clarification, (Primes & Perfect numbers less than 1 million)

I convinced them not to write an alogrithm in TSQL and that ideally you would have a table of Prime & Perfect numbers and just JOIN to those tables when needed.

"How do we fill the Prime table?", was the obvious next question.

This is surprisingly simple thanks to the Internet...
Prime Site This sight has a list of Prime numbers...

A simply parse and a BCP and we have a 100,000 row Prime table.

But it did get me thinking.. If we had a Numbers table with numbers 1 to 1 million, could we write a SQL statement to find the Primes or Perfect Numbers?

I am going to stick with numbers below a 1000 for the solution..

And allow 2 exceptions, those being the primes 1 & 2!!!!

Below is the code for the numbers table (Only to 1000)

CREATE TABLE Numbers(Number INT NOT NULL PRIMARY KEY CLUSTERED)

GO

DECLARE @i INT

SET @i = 1

WHILE @i < 1001

BEGIN

INSERT Numbers(Number) values (@i)

SET @i = @i + 1

END

GO

Now for the SQL Stuff

**--Prime Numbers **

SELECT X.Number as Primes

FROM Numbers N CROSS JOIN Numbers X

WHERE X.Number%N.Number != 0 AND X.Number > 1

AND N.Number > 0 AND N.Number < X.Number and X.Number%2 !=0

GROUP BY X.Number

HAVING (X.Number - Count(*)) = 2

**--Perfect Numbers **

SELECT X.Number as Perfect

FROM Numbers N CROSS JOIN Numbers X

WHERE X.Number%N.Number = 0 and X.Number > 1

AND N.Number < X.Number AND N.Number > 0

GROUP BY X.Number

HAVING SUM(N.Number) = X.Number

There seems to be an uncanny likeness between the 2...

I am interested in all other non-cursor solutions..

## Feedback

## # Whoops

left by Dave at 11/4/2003 4:02 AM...but if you add in: And X.Number%3!=0, it accomplishes the same thing and is faster. If you put in the %2!=0, might as well include the %3.

BTW - Nice post. This is a fun SQL problem.

## # re: SQL and the search for Prime and Perfect numbers

left by DavidM at 11/4/2003 9:40 AMIf I add the %3 condition then I exclude the number 3. So an OR is required.. It now looks like this..

And (X.Number%3!=0 OR X.Number=3)

The big penalty is obviously the CROSS JOIN so any reduction there is great. The modified plan produced 33% less intermediate rows..

I have also been trying to implement another shortcut.. N.Number < SQRT(X.Number).. But the HAVING clause needs to be modified to I don't know what!

## # Prime Numbers

left by Stoad at 11/5/2003 12:26 AMon 5000 rows in the Numbers):

select * from numbers t where not exists(select 0

from numbers tt where t.number%tt.number=0 and

tt.number<t.number and tt.number>1)

## # re: SQL and the search for Prime and Perfect numbers

left by DavidM at 11/5/2003 8:19 AMWhen I test this on my box (5000 Numbers) it seems to be substantial slower than my original solution according to the execution plan...

The problem seems to be a SCAN on the t table...

## # Combine the two ideas!

left by dave at 11/5/2003 9:58 AMSELECT X.Number as Primes

FROM Numbers N CROSS JOIN Numbers X

WHERE X.Number%N.Number = 0

AND X.Number > 1

AND N.Number > 0

AND N.Number <= Sqrt(X.Number)

and X.Number%2 !=0

GROUP BY X.Number

HAVING (Count(*)) = 1

## # More Maths...

left by DavidM at 11/11/2003 1:17 PM## # re: SQL and the search for Prime and Perfect numbers

left by Emerson KP at 8/26/2005 6:04 PMSELECT X.NO as Primes

FROM Numbers N CROSS JOIN Numbers X

WHERE MOD(X.NO,N.NO) != 0

AND N.NO < X.NO

GROUP BY X.NO

HAVING (X.NO - Count(*)) = 2

## # re: SQL and the search for Prime and Perfect numbers

left by Prabir at 3/21/2007 12:32 AM## # re: SQL and the search for Prime and Perfect numbers

left by Dao Viet Cuong at 4/27/2010 8:57 PMwith q as (select rownum+:n0-1 n from dual connect by level <:n-:n0)

select n as Prime from q

where n >= 2

and not exists (select *

from (select rownum+1 n2 from dual connect by level <:n-:n0)

where

n2 <= n/2

and mod(n, n2)=0

)

order by n