SQL and the search for Prime and Perfect numbers

I got an usual request today in reference to writing SQL statements to find Prime & 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..

Print | posted on Thursday, October 30, 2003 3:12 PM

Feedback

# Whoops

left by Dave at 11/4/2003 4:02 AM Gravatar
Actually that last suggestion was slower :)

...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 AM Gravatar
Thanks Dave.

If 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 AM Gravatar
Seems this works much faster (tested
on 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 AM Gravatar
Thanks Stoad.

When 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 AM Gravatar
So I just combined your two ideas to make the query a bit faster. Best I can do for now is:

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 <= 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 Gravatar

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

left by Emerson KP at 8/26/2005 6:04 PM Gravatar
Sql for prime nos

SELECT 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 Gravatar
gud Query

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

left by Dao Viet Cuong at 4/27/2010 8:57 PM Gravatar
/*Prime Numbers between n0 and n*/
with 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
Comments have been closed on this topic.