Click here to monitor SSC
Joe Celko

Celko's Summer SQL Stumpers: Prime Numbers

23 July 2009

Joe Celko kicks off our series of Summer SQL Stumpers with a challenge to improve on his solution to calculating the prime numbers between 1 and 10000. Once the various solutions have been contributed and judged, the winner of a $100 Amazon Voucher will be announced. The competition will be run on Simple-Talk and SQL Server Central together.

A PRIME SQL PUZZLE

I was teaching SQL classes for YAPC-10 (“Yet Another PERL Conference” #10) at Carnegie Mellon University at the end of June 2009.  For the record, I have never used PERL and had to Google up an overview before I went; it is a very different creature from SQL. 

One of my students asked if you could write an SQL statement to generate the prime numbers less than 1000 (or any other limit) that scales well.  He was bothered by the lack of loops in SQL and a Prime Number sieve is a common PERL programming exercise.  You can Google it and see an animation at Eratosthenes' sieve and some PERL code at Sieve of Eratosthenes with closures

My immediate answer was “sure, but you might have to use a recursive CTE to replace the loop.  Later I realized that was a really bad answer; you don’t need recursion, just a little math.  There are two useful facts from Number Theory:

  1. The prime factors of a given number (n) cannot be greater than ceiling (√n).  Think about it; by definition (√n * √n)) = n, and by definition, ceiling (√n) >= floor(√n) so integer rounding up will be safe.  This says that if I look at (a * b = c) where (a < b), then I don’t have to look at (b * a = c), so I can start searching for prime factors with small values. 
  2. All primes are of the form (6 * n ± 1), but not all number of that form are Primes.  For example (n = 1) gives us {5, 7} and they are both primes.  But for (n = 4) gives us {23, 25} where (25 = 5 * 5).  What this does is remove the multiples of 2 and 3 from consideration.

Let’s get all of that into SQL statements.  Let’s start with a table for the primes:

CREATE TABLE Primes
(p INTEGER NOT NULL PRIMARY KEY
  CHECK
(p > 1));

Now, your puzzle is to fill the table up to some limit, say 1000 just to keep it simple. 

 ANSWERS:

Let’s assume we have a table named Sequence with integers from 1 to (n) that we can use.  This is a common SQL programming idiom, so you don’t have to feel bad about using it.

CREATE TABLE Sequence
(seq INTEGER NOT NULL PRIMARY KEY
CHECK (seq  > 0));

There are lots of ways of filling this table, but here is one I like:

WITH Digits(i)
AS (SELECT i
  
FROM (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (0)) AS X(i))
INSERT INTO Sequence(seq)
SELECT
(D3.i * 1000 + D2.i * 100 + D1.i * 10 + D0.i + 1) AS seq
    
FROM Digits AS D0, Digits AS D1, Digits AS D2, Digits AS D3;

This template is easy to extend and the “.. + 1” gets rid of the zero. 

ANSWER #1

For the first attempt, let’s load the Primes table with candidate numbers using math fact #2 from above. 

INSERT INTO Primes (p)
(
SELECT (6 * seq) + 1
  
FROM Sequence
WHERE (6 * seq) + 1 <= 1000
UNION ALL
SELECT (6 * seq) - 1
  
FROM Sequence
WHERE (6 * seq) + 1 <= 1000);

An improvement which gets rid of the UNION ALL uses a table constant:

INSERT INTO Primes (p)
SELECT (6 * seq) + S.switch
  
FROM Sequence
      
CROSS JOIN
     
(SELECT switch
        
FROM (VALUES (-1), (+1))
      
AS F(switch))S
  
WHERE (6 * seq) + 1 <= 1000;

Now we have too many rows in Primes and need to remove the non-primes.  Now math fact #1 can come into play; test the set of numbers less than the square root to see if there is a factor among them. 

DELETE FROM Primes
WHERE EXISTS
  (
SELECT *
    
FROM Primes AS P1
    
WHERE P1.p <= CEILING (SQRT (Primes.p))
      AND
(Primes.p % P1.p) = 0);

ANSWER #2

Another way to load the candidates into Primes is to have the first few known primes hardwired into a query.  This is a generalization of the math fact #2, which dealt with multiples of only 2 and 3. 

INSERT INTO Primes (p)
SELECT seq
  
FROM Sequence
  
WHERE 0 NOT IN (seq % 2, seq % 3, seq % 5, seq % 7, .. );

The idea is that if we can limit the candidate set for Primes, performance will improve.  At the extreme, if the list of “MOD (seq, <prime>)” expressions goes to a value equal or higher than the upper limit we are looking at, we get the answer immediately.

This is a good trick; many SQL programmers think that an IN() list can only be constants.  You might also want to look at how many values it can hold –It is larger than you think. 

Another candidate pruning trick is based on the math fact that integers with final digits {2, 4, 6, 8, 0} are even numbers; those with final digits {5, 0} are multiples of five. Let’s not look at them when we build a candidate table.

WITH Digits(i)
AS (SELECT i
  
FROM (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (0)) AS X(i)
   )
INSERT INTO Sequence(seq)
SELECT (D3.i * 1000 + D2.i * 100 + D1.i * 10 + Units.i)
  
FROM (SELECT i
  
FROM (VALUES (1), (3), (7), (9)) AS X(i)) AS Units,
      
Digits AS D1, Digits AS D2, Digits AS D3

ANSWER #3

Another approach is to generate all of the non-primes and remove them from the Sequence table.

INSERT INTO Primes (p)
(SELECT seq FROM Sequence WHERE seq <= 1000)
EXCEPT
(SELECT (F1.seq * F2.seq) AS composite_nbr
  
FROM Sequence AS F1, Sequence AS F2
WHERE F1.seq BETWEEN 2 AND CEILING (SQRT (1000))
  AND
F2.seq BETWEEN 2 AND CEILING (SQRT (1000))
  AND
F1.seq <= F2.seq
  
AND (F1.seq * F2.seq) <= 1000)

Obviously, the Sequence table in the left hand clause could be anyone of the trimmed candidate tables we previously constructed.  

What answers to do you have? As a hint, there are faster but more complicated algorithms, like the Sieve of Atkin and the various Wheel Sieves.

We have attached files containing code that runs in SQL 200 SQL 2005 and SQL 2008. Joe's code in the article  has been fixed to run in SQL 2008.

The best answer to each stumper will be given a prize of a $100 Amazon voucher. The stumper will be run simultaneously on  SQL Server Central and Simple-Talk. To see all the comments so far, you will need to visit both sites. We will take entries for a week after the first Monday of publication,  posted as comments to the articles. Two weeks after the challenge is sent out, the judge's decision and comments will be sent out in the newsletter, and published on the site.

Joe Celko and Phil Factor will judge the answers to this puzzle. Your answer should :
   1) Solve the problem -- Duh!
   2) Avoid proprietary features in SQL Server that will not port or be good across
        all releases, present and future.
   3) Use Standard features in SQL Server that will be good across all releases,
        present and future. Extra points for porting code.
   4) Be clever but not obscure.
   5) Explain how you got your answer.  

Joe Celko

Author profile:

Joe Celko is one of the most widely read of all writers about SQL, and was the winner of the DBMS Magazine Reader's Choice Award four consecutive years. He is an independent consultant living in Austin, TX. He has taught SQL in the US, UK, the Nordic countries, South America and Africa.
He served 10 years on ANSI/ISO SQL Standards Committee and contributed to the SQL-89 and SQL-92 Standards.
He has written over 800 columns in the computer trade and academic press, mostly dealing with data and databases. He is the author of eight books on SQL for Morgan-Kaufmann, including the best selling SQL FOR SMARTIES.
Joe is a well-known figure on Newsgroups and Forums, and he is famous for his his dry wit. He is also interested in Science Fiction.

Search for other articles by Joe Celko

Rate this article:   Avg rating: from a total of 13 votes.


Poor

OK

Good

Great

Must read
Have Your Say
Do you have an opinion on this article? Then add your comment below:
You must be logged in to post to this forum

Click here to log in.


Subject: Primes under 10,000
Posted by: Phil Factor (view profile)
Posted on: Sunday, July 26, 2009 at 8:48 AM
Message:
--This just takes Joe's hint about only needing to
--test numbers less than the square root for a
--modulus of 0 but does the trick with an inner
--join with a slightly unusual join condition

SELECT
1 AS [prime]
UNION
SELECT
2
UNION
SELECT
prime
FROM   ( SELECT s.seq AS [prime]
          
FROM   Sequence s
              
INNER JOIN Sequence f
              
ON f.seq BETWEEN 2
                  
AND CEILING(SQRT(s.seq))
          
GROUP BY  s.seq
          
HAVING    MIN(s.seq % f.seq) > 0
        
) AS [TheRest]
ORDER BY prime
--whee! I enjoyed this

Subject: Isn't 3 a prime
Posted by: Matthew (view profile)
Posted on: Sunday, July 26, 2009 at 9:48 PM
Message: I'd never heard of the (6 * n ± 1) formula before.
What about 2 and 3, both of which are prime but do not match the 6n±1 form.

Subject: Another quick method
Posted by: Jonathan Kehayias (view profile)
Posted on: Sunday, July 26, 2009 at 9:52 PM
Message:

This would work on all versions of SQL


SELECT 1
    
UNION ALL
SELECT 2
    
UNION ALL
SELECT nums.n
    
FROM
    
(
    
SELECT number AS p
        
FROM spt_values
        
WHERE TYPE = 'p'
            
AND number BETWEEN 2
            
AND 35
    
) AS pns,
    (
    
SELECT number AS n
        
FROM spt_values
        
WHERE TYPE = 'p'
            
AND number BETWEEN 1
            
AND 1000
    
) AS nums
    
WHERE pns.p < nums.n
        
AND pns.p <> nums.n
    
GROUP BY nums.n
    
HAVING MIN(nums.n % pns.p) > 0

Subject: An ugly solution
Posted by: Theo Spears (not signed in)
Posted on: Monday, July 27, 2009 at 4:46 AM
Message: --Here is an ugly solution, but it is reasonably quick.

SELECT seq p INTO #Space FROM Sequence WHERE seq > 1;
CREATE TABLE Primes (p INTEGER NOT NULL PRIMARY KEY);

DECLARE @Highest INT
SET
@Highest = 1

WHILE ( SELECT COUNT(*) FROM #Space ) > 0
  
BEGIN
    INSERT  INTO
Primes
        
SELECT  *
        
FROM  #Space
        
WHERE   p < POWER(
                   (
SELECT  MIN(p) FROM #Space AS s ),
                  
2)
    
DELETE  FROM #Space
    
WHERE   p IN ( SELECT   f.p * Multiples.seq
            
FROM   Primes AS f
                
CROSS JOIN ( SELECT seq
                      
FROM   Sequence
                      
WHERE  seq <= FLOOR(
                            (
SELECT MAX(p)
                              
FROM #Space ) / @Highest)
                          AND
seq >= @Highest
                      
UNION
                       SELECT
1
                      
) Multiples
            
WHERE  f.p >= @Highest )
    
SET @Highest = ( SELECT MAX(p) FROM Primes )
  
END

SELECT
* FROM Primes



Subject: Prime numbers (plain DB2)
Posted by: Leonid_Khiger_at_Citigroup (not signed in)
Posted on: Monday, July 27, 2009 at 6:37 AM
Message: WITH
limit (lim) AS
(SELECT INT(100000) FROM sysibm.sysdummy1
)
,
numbers (num) AS
(SELECT 2 FROM sysibm.sysdummy1
UNION ALL
SELECT num + 1 FROM numbers, limit
WHERE num + 1 &amp;lt;= INT(SQRT(lim)) + 1
)
,
prime_check (prime_num, prime_ind) AS
(SELECT INT(2), VARCHAR('P', 1) FROM sysibm.sysdummy1
UNION ALL
SELECT 3, 'P' FROM sysibm.sysdummy1
UNION ALL
SELECT prime_num + 2,
CASE
WHEN
1 = (SELECT 1 FROM sysibm.sysdummy1
WHERE
EXISTS
(
SELECT 1 FROM numbers
WHERE num &amp;lt;= INT(SQRT(prime_num)) + 1
AND
prime_num + 2 = INT((prime_num + 2) / num) * num ) )
THEN 'R'
ELSE 'P'
END
FROM
prime_check, limit
WHERE
prime_num + 2 &amp;lt;= INT(SQRT(lim)) + 1
)
,
prime_num_1 (prime_num) AS
(SELECT prime_num FROM prime_check
WHERE prime_ind = 'P'
)
,
prime_check_2 (prime_num, prime_ind) AS
(SELECT MAX(prime_num), VARCHAR('X', 1)
FROM prime_num_1
UNION ALL
SELECT p2.prime_num + 2,
CASE
WHEN
1 = (SELECT 1 FROM sysibm.sysdummy1
WHERE EXISTS
(
SELECT 1 FROM prime_num_1 p1
WHERE p1.prime_num &amp;lt;= INT(SQRT(p2.prime_num)) + 1
AND
p2.prime_num + 2= INT((p2.prime_num + 2) / p1.prime_num ) * p1.prime_num ) )
THEN 'R'
ELSE 'P'
END
FROM
prime_check_2 p2, limit lm
WHERE
p2.prime_num + 2 &amp;lt;= lim
)
,
prime_number (prime_num) AS
(SELECT * FROM prime_num_1
UNION ALL
SELECT prime_num FROM prime_check_2
WHERE prime_ind = 'P'
)
SELECT prime_num "Prime Number" FROM prime_number



I used the cascade method:

1. Find all prime numbers which is <= sqrt(lim)
2. Find all prime numbers which is > sqrt(lim) and <= lim

3. you can find discussion about my solution here:
http://www.dbforums.com/db2/1645635-prime-numbers-plain-db2.html

4. Special thanks to user r937 who gave me your site

5. This SQL is working and could be simply transform to other SQL languages

Leonid Khiger (Citigroup, NY-NJ)

(Ed: We colorized it and capitalized keywords just to make it easier to follow for SQL Server users)

Subject: (6 * n ± 1) formula
Posted by: karthi_sql2005@yahoo.co.in (view profile)
Posted on: Monday, July 27, 2009 at 6:51 AM
Message: Can't we use any other number here?

Subject: I must be doing something wrong...
Posted by: Jason Miller (not signed in)
Posted on: Monday, July 27, 2009 at 7:01 AM
Message: I took the 3rd option (SQL2005) and tested it, with slight modifications... I have a Tally table with 1M rows, created from the parsing example...
DECLARE @l INT
SELECT
@l = 1000000


(SELECT n FROM flib..tally WHERE n <= @l )
EXCEPT
(SELECT (F1.n * F2.n ) AS composite_nbr
  
FROM flib..tally AS F1, flib..tally AS F2
WHERE F1.n BETWEEN 2 AND CEILING (SQRT (@l))
  AND
F2.n BETWEEN 2 AND CEILING (SQRT (@l))
  AND
F1.n <= F2.n
  
AND (F1.n * F2.n) <= @l)
ORDER BY 1


The part I'm getting lost on is...
I'm finding non-primes in the output.
The first few of hundred numbers look ok, but I started seeing odd balls like 2018, 2026, 2038, and so on.

This is troubling.
So I compared the results to a table of prime numbers that I generated using some old code and verified by our reside mathematician. For a limit of L = 1M, it found 673,588 false primes and only 78,498 true primes.



For review, the old code is:
USE trace
GO



CREATE TABLE prime_numbers (
  
num   BIGINT NOT NULL UNIQUE )
GO
CREATE CLUSTERED INDEX iClstrd ON prime_numbers ( Num )
GO
INSERT prime_numbers VALUES ( 1 )
INSERT prime_numbers VALUES ( 2 )
INSERT prime_numbers VALUES ( 3 )
GO


CREATE PROC pn
  
@seconds INT = 3600
AS
BEGIN
SET NOCOUNT ON

DECLARE
@i  BIGINT,
  
@test BIGINT,
  
@x DATETIME ,
  
@rt   dec ( 38,12 )


SELECT @i = MAX( a ) FROM prime_numbers
SELECT @x = DATEADD( ss, @seconds, GETDATE() )

WHILE @x > GETDATE()
BEGIN

  SELECT  
@test = 3 ,   -- Pick a new candiate, and set the initial test number.
    
@i = @i + 2   -- Primes will never be even...

  
IF ( @i % 10 ) = 5    -- No prime will ever end in "5"...
    
SELECT   @i = @i + 2

  
SELECT @rt = SQRT( @i )

  
WHILE CONVERT( INT , @rt ) = @rt -- find natural roots...
    
SELECT   @i = @i + 2 ,
        
@rt = SQRT( @i )

  
WHILE @test <= @rt
  
BEGIN
     IF
@i % @test = 0
        
SELECT @test = @i -- Found a root. Set test to candidate so loop quits.
    
ELSE
        SELECT
@test = MIN( a ) FROM prime_numbers WHERE a > @test
  
END

  IF
@test != @i
    
INSERT INTO prime_numbers VALUES ( @i )
END

END
GO



Subject: defense of the 6n+-1 formula
Posted by: Tamás Hajdu (not signed in)
Posted on: Monday, July 27, 2009 at 7:23 AM
Message: It is known from Dirichlet that a + nd, where n ≥ 0 series contains infinite number of primes. (http://en.wikipedia.org/wiki/Dirichlet's_theorem_on_arithmetic_progressions)
6n+3 and 6n-3 series don't contain primes because 3 is a divider in both series. (of course n=0, then 3 is a prime, but this is the only one).
6n+2 and 6n-2 similar to this, 2 is a divider. 6n is not prime because 2,3,6 is divider.
So we left only 6n+1 and 6n-1 series together with Dirichlet theorem and of course 2, and 3. These 2 primes comes from the n=0 cases of the 6n+2 and 6n+3 series.
6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n-1 series covers the whole N (positive integer numbers)

Subject: Use the webservice
Posted by: Matt (view profile)
Posted on: Monday, July 27, 2009 at 7:48 AM
Message: This seems to be a computationally intensive task which isn't really database orientated.
Although I admire the answers on academic level, perhaps a more appropriate answer would be to handle this task at the webservice layer or using a data loading tool.

Subject: Prime numbers (plain DB2) -- 2
Posted by: Leonid_Khiger_at_Citigroup (not signed in)
Posted on: Monday, July 27, 2009 at 9:35 AM
Message: More compact view.
I replace num = p * (num / p) by mod(num, p) = 0:

WITH
limit (lim) AS
(SELECT INT(100000) FROM sysibm.sysdummy1
)
,
numbers (num) AS
(SELECT 2 FROM sysibm.sysdummy1
UNION ALL
SELECT num + 1 FROM numbers, limit
WHERE num + 1 <= INT(SQRT(lim)) + 1
)
,
prime_check (prime_num, prime_ind) AS
(SELECT INT(2), VARCHAR('P', 1) FROM sysibm.sysdummy1
UNION ALL
SELECT 3, 'P' FROM sysibm.sysdummy1
UNION ALL
SELECT prime_num + 2,
CASE
WHEN
1 = (SELECT 1 FROM sysibm.sysdummy1
WHERE EXISTS
(
SELECT 1 FROM numbers
WHERE
num <= INT(SQRT(prime_num)) + 1
AND mod(prime_num + 2, num) = 0 ) )
THEN 'R' ELSE 'P'
END
FROM
prime_check, limit
WHERE
prime_num + 2 <= INT(SQRT(lim)) + 1
)
,
prime_num_1 (prime_num) AS
(SELECT prime_num FROM prime_check
WHERE prime_ind = 'P'
)
,
prime_check_2 (prime_num, prime_ind) AS
(SELECT MAX(prime_num), VARCHAR('X', 1)
FROM prime_num_1
UNION ALL
SELECT p2.prime_num + 2,
CASE
WHEN
1 = (SELECT 1 FROM sysibm.sysdummy1
WHERE EXISTS
(
SELECT 1 FROM prime_num_1 p1
WHERE
p1.prime_num <= INT(SQRT(p2.prime_num)) + 1
AND mod(p2.prime_num + 2, p1.prime_num) = 0 ) )
THEN 'R' ELSE 'P'
END
FROM
prime_check_2 p2, limit lm
WHERE
p2.prime_num + 2 <= lim
)
,
prime_number (prime_num) AS
(SELECT * FROM prime_num_1
UNION ALL
SELECT prime_num FROM prime_check_2
WHERE prime_ind = 'P'
)
SELECT prime_num "Prime Number" FROM prime_number


Lenny K.

Subject: Brute force? But were we supposed to avoid the "WHILE"?
Posted by: Absinthe (view profile)
Posted on: Monday, July 27, 2009 at 9:36 AM
Message: SET NOCOUNT ON
DECLARE
@Primes TABLE
(
    
Val INT
)

DECLARE @ctr INT

/*
if we hard code the 2 here then we can increment by 2 below, otherwise
this still works if we start @Ctr at 2 and increment by 1
*/
INSERT INTO @Primes (Val) VALUES (2)
SET @ctr = 3

WHILE @ctr < 10000
BEGIN

    INSERT INTO
@primes (Val)
        
SELECT @ctr
        
WHERE  NOT EXISTS
               (
SELECT *
                
FROM @primes
                
WHERE @ctr % Val = 0)
    
    
SELECT @ctr = @ctr+2
END

SELECT
* FROM @primes



WHILE @x > GETDATE()
BEGIN

   SELECT  
@test = 3 ,   -- Pick a new candiate, and set the initial test number.
      
@i = @i + 2   -- Primes will never be even...

  
IF ( @i % 10 ) = 5    -- No prime will ever end in "5"...
      
SELECT  @i = @i + 2

  
SELECT @rt = SQRT( @i )

  
WHILE CONVERT( INT , @rt ) = @rt -- find natural roots...
      
SELECT  @i = @i + 2 ,
          
@rt = SQRT( @i )

  
WHILE @test <= @rt
  
BEGIN
       IF
@i % @test = 0
          
SELECT @test = @i -- Found a root. Set test to candidate so loop quits.
      
ELSE
           SELECT
@test = MIN( a ) FROM num WHERE a > @test
  
END

   IF
@test != @i
      
INSERT INTO prime_numbers VALUES ( @i )
END

END
GO




Subject: My attempt (19 secs for 1-10000)
Posted by: Brian V (not signed in)
Posted on: Monday, July 27, 2009 at 10:41 AM
Message:
SET NOCOUNT ON

--GET PRIME NUMBERS
DECLARE @startvalue AS INT
DECLARE
@endvalue AS INT

SET
@startvalue = 1
SET @endvalue = 10000

DROP TABLE #input

CREATE TABLE #input
  
(Numbers INT)
  
WHILE @startvalue <= @endvalue
  
BEGIN
   INSERT INTO
#input    
      
SELECT @startvalue
  
SET @startvalue = @startvalue + 1
  
END

DROP TABLE
#output

CREATE TABLE #output
  
(primenumber INT)


DECLARE getvalues CURSOR FOR
   SELECT
numbers FROM #input

OPEN getvalues

DECLARE @number AS INT
DECLARE
@testvalue AS INT
DECLARE
@result AS INT
  
FETCH
next FROM getvalues INTO @number  

WHILE @@FETCH_STATUS = 0
  
BEGIN
   SET
@result = 0
  
  
SET @testvalue = 2
  
WHILE @testvalue < @number
      
BEGIN
       IF
@number % @testvalue  = 0
          
BEGIN
               SET
@result = 1
              
BREAK
           END
       SET
@testvalue = @testvalue + 1
      
END
      
       IF
@result = 0
          
INSERT INTO #output  
              
SELECT @number
      
  
FETCH next FROM getvalues INTO @number  
  
END
  
CLOSE
getvalues
DEALLOCATE getvalues    

SELECT *
  
FROM #output

Subject: How I handled it
Posted by: dgrace (view profile)
Posted on: Monday, July 27, 2009 at 11:40 AM
Message: SELECT prime_number FROM Primes WHERE prime_number <= 1000

That's how I would generate the set of primes less than 1000. I used something else (forget what) to populate the table but, why would I want to run that code more than once?

Set Theory FTW!

David

Subject: My Solution
Posted by: Adam Haines (view profile)
Posted on: Monday, July 27, 2009 at 12:16 PM
Message: I chose to use not exists. Essentially this method uses the correlation between the current number and the lesser number. If a modulo value exists between the current number and the lesser number, the number is not prime.
SELECT s1.seq AS PrimeNumbers
FROM [dbo].[Sequence] s1
WHERE
  
(s1.seq > 1 AND s1.seq < 10000)
   AND (
s1.seq % 2 = 1 OR s1.seq = 2)
   AND NOT EXISTS(
      
SELECT 1
      
FROM [dbo].[Sequence] s2
      
WHERE
          
(s2.seq < s1.seq AND s2.seq > 1)
           AND
s1.seq % s2.seq = 0      
      
)
ORDER BY s1.[seq]

I think it would be beneficial to have another column in the sequence table, that houses Prime candidates, so you can not process numbers that you know will not be Prime, such as even numbers greater than 2.

Subject: I think I figured out the issue
Posted by: Jason Miller (not signed in)
Posted on: Monday, July 27, 2009 at 12:48 PM
Message: The third example uses:

INSERT INTO Primes (p)
(
SELECT seq FROM Sequence WHERE seq <= 1000)
EXCEPT
(SELECT (F1.seq * F2.seq) AS composite_nbr
  
FROM Sequence AS F1, Sequence AS F2
WHERE F1.seq BETWEEN 2 AND CEILING (SQRT (1000))
  AND
F2.seq BETWEEN 2 AND CEILING (SQRT (1000))
  AND
F1.seq <= F2.seq
  
AND (F1.seq * F2.seq) <= 1000)


I believe the issue has to do with the two lines:

WHERE F1.seq BETWEEN 2 AND CEILING (SQRT (1000))
  AND
F2.seq BETWEEN 2 AND CEILING (SQRT (1000))

If you're searching for numbers with a limit of 5000, you're limiting your search to both numbers being less than or equal to 71. So the combination of 3 and 293 will never show up. Which would make 879 appear to be prime. Or any number multiplied by a number greater than the square root of the limit...

I think if you eliminate the second line, all will be right.


(Sorry for the multiple errors in the previous post. I did a poor job copy-n-pasting.)








Subject: good for small, not as scalable as it could be
Posted by: Matt (view profile)
Posted on: Monday, July 27, 2009 at 1:36 PM
Message: This script is not as scalable as it could be, but I feel it is readable. On the box I am using, inserts for Primes <= 100 in less than 1 second, Primes <= 1000 in 25 seconds, and Primes <= 100,000 in about 5 minutes. The box was under heavy load during testing.

INSERT INTO Primes(p)
SELECT nPrime.seq
FROM Sequence nPrime
    
LEFT JOIN Sequnce nFactor
      
ON nFactor.seq >= 2 --do not include seq=1 as a factor
    
AND nFactor.seq <= CEILING(SQRT(nPrime.seq))
     AND
nPrime.seq % nFactor.seq = 0
    
AND nFactor.seq <> nPrime.seq --criteria to allow for 2 as a prime number
WHERE (nPrime.seq < 10 OR nPrime.seq % 10 NOT IN (0,2,4,6,8,5)) --limits comparisons to non-even, non-multiples of 5
  
AND nFactor.seq IS NULL
   AND
nPrime.seq > 1 --do not include 1 as a prime number
  
AND nPrime.seq <= 100 --cap for determining prime numbers under a certain level, change this to change the range





Subject: primes to 1 million
Posted by: MikeD (not signed in)
Posted on: Monday, July 27, 2009 at 6:41 PM
Message: /*
select top 1000000
[N] = identity(int,1,1)
into
#seq
from
dbo.syscolumns a with (nolock)
,dbo.syscolumns b with (nolock)
,dbo.syscolumns c with (nolock)
create clustered index ix_seqN on #seq ([N])

create table prime ([N] int)
CREATE INDEX ix_N on prime ([N])
insert into prime ([N]) values (2)
insert into prime ([N]) values (3)
*/

insert into prime ([N])
select
a.[N]
from
#seq a
left join
prime p
on a.[N] % p.[N] = 0
cross join
(select max([N]) as [mxprime] from prime) mxp
where
a.[N] > mxp.[mxprime]
and
a.[N] < mxp.[mxprime]*mxp.[mxprime]
and
a.[N] % 2 != 0 /* no multiples of 2 */
and
a.[N] % 3 != 0 /* no multiples of 3 */
and
p.[N] is null

select [countN]=count(*),[maxN] = max([N]) from prime

explain:
- run commented code once (setup) and run the insert([batch]) 4 times, each run exponentially adds to the 'prime' table up to the maximum of the tally table (#seq)
- strategy is simple: find candidates that are not multiples of 2 or 3 and do not have factors already in the primes list; add found primes to the 'prime' table.
- I really wanted to use recursive CTE to do this, but there is apparently a rule preventing outer join in CTE recursion. Anyway, this solution does work on msSQL2000.
- Timing will vary (of course) but this solution checks 1 million candidates in under 2 minutes (my threshold for waiting for a query to complete)

Subject: Sieve in TSQL
Posted by: brandonh6k (view profile)
Posted on: Monday, July 27, 2009 at 7:07 PM
Message: Pretty darn ugly TSQL, but it's quick for small sets (limit of 10000 processed in 6 seconds). Used a functional implementation of a inverted sieve from http://diditwith.net/2009/01/20/YAPESProblemSevenPart2.aspx as my inspiration.

----

SET NOCOUNT ON

DECLARE @Primes table (prime bigint)
DECLARE @Sieve table (number bigint)
DECLARE @Factors table (number bigint, factor bigint)

DECLARE @limit int, @current int
SET @limit = 1000
SET @current = 2
WHILE @current < @limit
BEGIN
IF NOT EXISTS(SELECT * FROM @Sieve WHERE number = @current)
BEGIN
INSERT INTO @Primes SELECT @current
INSERT INTO @Sieve SELECT SQUARE(@current)
INSERT INTO @Factors SELECT SQUARE(@current), @current
END
ELSE
BEGIN
DECLARE @currentFactor bigint
SET @currentFactor = (SELECT MIN(factor) FROM @factors WHERE number = @current)
WHILE @currentFactor IS NOT NULL
BEGIN
DECLARE @newNumber bigint
SET @newNumber = @currentFactor + @current
IF NOT EXISTS(SELECT * FROM @Sieve WHERE number = @newNumber)
INSERT INTO @Sieve SELECT @newNumber
INSERT INTO @Factors SELECT @newNumber, @currentFactor
SET @currentFactor = (SELECT MIN(factor) FROM @factors WHERE number = @current AND factor > @currentFactor)
END
DELETE FROM @Sieve WHERE number = @current
DELETE FROM @Factors WHERE number = @current
END
SET @current = @current + 1
END

SELECT * FROM @Primes

Subject: Brute force? But were we supposed to avoid the "WHILE"?
Posted by: Absinthe (view profile)
Posted on: Tuesday, July 28, 2009 at 7:16 AM
Message: SET NOCOUNT ON
DECLARE @Primes TABLE
(
Val int
)

DECLARE @ctr int

/*
if we hard code the 2 here then we can increment by 2 below, otherwise
this still works if we start @Ctr at 2 and increment by 1
*/
INSERT INTO @Primes (Val) VALUES (2)
SET @ctr = 3

WHILE @ctr < 10000
BEGIN

INSERT INTO @primes (Val)
SELECT @ctr
WHERE NOT EXISTS
(SELECT *
FROM @primes
WHERE @ctr % Val = 0)

SELECT @ctr = @ctr+2
END

SELECT * FROM @primes

Subject: This must be wrong; it looks too simple
Posted by: Lee (view profile)
Posted on: Tuesday, July 28, 2009 at 10:59 AM
Message: INSERT INTO Primes (p)
SELECT s1.seq
FROM Sequence s1
WHERE s1.seq != 1
AND NOT EXISTS (SELECT 1
FROM Sequence s2
WHERE s2.seq BETWEEN 2 AND SQRT (s1.seq)
AND s1.seq % s2.seq = 0)

Subject: This must be wrong; it looks too simple, con't.
Posted by: Lee (view profile)
Posted on: Tuesday, July 28, 2009 at 12:20 PM
Message: By the way, the method I posted just above inserts 78498 rows of prime numbers between 2 and 999983 into table 'Primes' on my dev box here in 58 seconds. I sure hope that's correct because I have enough egg on my face from previous contests.

Subject: Brute force improved
Posted by: Anonymous (not signed in)
Posted on: Tuesday, July 28, 2009 at 3:34 PM
Message: DECLARE @Primes TABLE
(
Prime INT
)

DECLARE @Candidate INT,
@Increment INT

SELECT @Candidate = 5,
@Increment = 2

WHILE @Candidate <= 10000
BEGIN
INSERT @Primes
(
Prime
)
SELECT @Candidate
WHERE NOT EXISTS (SELECT * FROM @Primes WHERE @Candidate % Prime = 0)

SELECT @Candidate = @Candidate + @Increment,
@Increment = 6 - @Increment
END

SELECT 2 AS Prime UNION ALL
SELECT 3 UNION ALL
SELECT Prime
FROM @Primes

Subject: Another quick method
Posted by: Jonathan Kehayias (view profile)
Posted on: Tuesday, July 28, 2009 at 4:54 PM
Message: This would work on all versions of SQL:

select 1
union all
select 2
union all
select nums.n
from
(
select number as p
from spt_values
where type = 'p'
and number between 2 and 35
) as pns,
(
select number as n
from spt_values
where type = 'p'
and number between 1 and 1000
) as nums
where pns.p < nums.n
and pns.p <> nums.n
group by nums.n
having min(nums.n%pns.p) > 0

Subject: Sieve Of Atkin implementation
Posted by: Peso (not signed in)
Posted on: Wednesday, July 29, 2009 at 5:03 PM
Message: /*
Peter Larsson
Ryan Randall
*/

-- Initialize user supplied parameter
DECLARE @MaxPrime INT

SET @MaxPrime = 1000000

-- Prepare helper variables
DECLARE @MaxNumber INT

SET @MaxNumber = SQRT(@MaxPrime)

-- Create staging tables
CREATE TABLE #Primes
(
Prime INT NOT NULL,
Prime2 BIGINT NOT NULL
)

CREATE TABLE #Sequence
(
Seq INT NOT NULL,
Seq2 BIGINT NOT NULL
)

CREATE UNIQUE CLUSTERED INDEX IX_Sequence ON #Sequence (Seq, Seq2)

INSERT #Sequence
(
Seq,
Seq2
)
SELECT n,
CAST(n AS BIGINT) * CAST(n AS BIGINT)
FROM (
SELECT 1
+ 1000 * COALESCE(d.Digit, 0)
+ 100 * COALESCE(c.Digit, 0)
+ 10 * COALESCE(b.Digit, 0)
+ COALESCE(a.Digit, 0) AS n
FROM (
SELECT 0 AS Digit UNION ALL
SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL
SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL
SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
) AS a
LEFT JOIN (
SELECT 0 AS Digit UNION ALL
SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL
SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL
SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
) AS b ON @MaxNumber > 10
AND 10 * b.Digit < @MaxNumber
LEFT JOIN (
SELECT 0 AS Digit UNION ALL
SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL
SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL
SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
) AS c ON @MaxNumber > 100
AND 100 * c.Digit < @MaxNumber
LEFT JOIN (
SELECT 0 AS Digit UNION ALL
SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL
SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL
SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
) AS d ON @MaxNumber > 1000
AND 1000 * d.Digit < @MaxNumber
WHERE a.Digit < @MaxNumber
) AS q
WHERE n <= @MaxNumber
ORDER BY n

INSERT #Primes
(
Prime,
Prime2
)
SELECT 2 AS k, 4 UNION ALL
SELECT 3, 9 UNION ALL
SELECT 5, 25 UNION ALL
SELECT k, CAST(k AS BIGINT) * CAST(k AS BIGINT)
FROM (
SELECT k
FROM (
SELECT 4 * a.Seq2 + b.Seq2 AS k
FROM #Sequence AS a
CROSS JOIN #Sequence AS b
) AS c
WHERE k <= @MaxPrime
AND k % 12 IN (1, 5)

UNION ALL

SELECT k
FROM (
SELECT 3 * a.Seq2 + b.Seq2 AS k
FROM #Sequence AS a
CROSS JOIN #Sequence AS b
) AS c
WHERE k <= @MaxPrime
AND k % 12 = 7

UNION ALL

SELECT k
FROM (
SELECT 3 * a.Seq2 - b.Seq2 AS k
FROM #Sequence AS a
INNER JOIN #Sequence AS b ON b.Seq < a.Seq
) AS c
WHERE k <= @MaxPrime
AND k % 12 = 11
) AS d
WHERE k % 10 IN (1, 3, 7, 9)
GROUP BY k
HAVING COUNT(k) IN (1, 3)
--ORDER BY k

CREATE UNIQUE CLUSTERED INDEX IX_Primes ON #Primes (Prime2, Prime)

SELECT p.Prime
FROM #Primes AS p
WHERE NOT EXISTS (
SELECT 1
FROM #Primes AS x
WHERE x.Prime2 <= p.Prime
AND p.Prime % x.Prime = 0
)
AND p.Prime <= @MaxPrime

DROP TABLE #Primes,
#Sequence

Subject: Prime Numbers
Posted by: parody (view profile)
Posted on: Friday, July 31, 2009 at 4:47 AM
Message: Hi this one intrigued me and has prompted my first post... here goes.

I started off using the formulas Joe suggested relating to primes but found I kept coming up with the same or simlar answers to those already posted. In an attempt to find something unique and somewhat "portable" as per the criteria I went back to basics and used some relatively simple logic on the "Sequence" table. That is that to be prime any number cannot be divisible by any number lesser than it other than 1:

SELECT Seq FROM Sequence Seq1
WHERE NOT EXISTS
(SELECT 1
FROM Sequence Seq2
INNER JOIN Sequence Seq3
ON Seq3.Seq > Seq2.Seq
WHERE Seq2.Seq <> 1
AND Seq3.Seq%Seq2.Seq = 0
AND Seq1.seq = Seq3.Seq)
AND Seq <> 1 --remove 1 as it is not prime
ORDER BY Seq

This gets all 1229 primes up to 10000 in 2 seconds in my environment.

Hope you like it!

By the way if anyone want to check their primes look here http://primes.utm.edu/lists/small/10000.txt


Subject: Prime Numbers
Posted by: parody (view profile)
Posted on: Friday, July 31, 2009 at 4:49 AM
Message: Hi this one intrigued me and has prompted my first post... here goes.

I started off using the formulas Joe suggested relating to primes but found I kept coming up with the same or simlar answers to those already posted. In an attempt to find something unique and somewhat "portable" as per the criteria I went back to basics and used some relatively simple logic on the "Sequence" table. That is that to be prime any number cannot be divisible by any number lesser than it other than 1:

SELECT Seq FROM Sequence Seq1
WHERE NOT EXISTS
(SELECT 1
FROM Sequence Seq2
INNER JOIN Sequence Seq3
ON Seq3.Seq > Seq2.Seq
WHERE Seq2.Seq <> 1
AND Seq3.Seq%Seq2.Seq = 0
AND Seq1.seq = Seq3.Seq)
AND Seq <> 1 --remove 1 as it is not prime
ORDER BY Seq

This gets all 1229 primes up to 10000 in 2 seconds in my environment.

Hope you like it!

By the way if anyone want to check their primes look here http://primes.utm.edu/lists/small/10000.txt


Subject: Prime Numbers
Posted by: parody (view profile)
Posted on: Friday, July 31, 2009 at 5:06 AM
Message: Hi this one intrigued me and has prompted my first post... here goes.

I started off using the formulas Joe suggested relating to primes but found I kept coming up with the same or simlar answers to those already posted. In an attempt to find something unique and somewhat "portable" as per the criteria I went back to basics and used some relatively simple logic on the "Sequence" table. That is that to be prime any number cannot be divisible by any number lesser than it other than 1:

SELECT Seq FROM Sequence Seq1
WHERE NOT EXISTS
(SELECT 1
FROM Sequence Seq2
INNER JOIN Sequence Seq3
ON Seq3.Seq > Seq2.Seq
WHERE Seq2.Seq <> 1
AND Seq3.Seq%Seq2.Seq = 0
AND Seq1.seq = Seq3.Seq)
AND Seq <> 1 --remove 1 as it is not prime
ORDER BY Seq

This gets all 1229 primes up to 10000 in 2 seconds in my environment.

Hope you like it!

By the way if anyone want to check their primes look here http://primes.utm.edu/lists/small/10000.txt


Subject: Prime Numbers
Posted by: parody (view profile)
Posted on: Friday, July 31, 2009 at 8:12 AM
Message: A slight improvement to the above to my post above to prevent checking more numbers than necessary using the square root theory.

SELECT Seq FROM Sequence Seq1
WHERE NOT EXISTS
(SELECT 1
FROM Sequence Seq2
INNER JOIN Sequence Seq3
ON Seq3.Seq > Seq2.Seq
WHERE Seq2.Seq < (SELECT SQRT(MAX(Seq)) FROM Sequence)
AND Seq2.Seq <> 1
AND Seq3.Seq%Seq2.Seq = 0
AND Seq1.seq = Seq3.Seq)
AND Seq <> 1 --remove 1 as it is not prime
ORDER BY Seq

I must admit it doesnt scale up well in terms of performance, e.g. against a 100000 sequence table. Strictly speaking though that wasnt one of the 5 points the answer should address... :-)

Subject: Prime Numbers
Posted by: parody (view profile)
Posted on: Friday, July 31, 2009 at 8:43 AM
Message: Better performance using a variable drasitcally lowers scan count.

DECLARE @MaxCheck tinyint
SET @MaxCheck = (SELECT SQRT(MAX(Seq)) FROM Sequence)

SELECT Seq FROM Sequence Seq1
WHERE Seq NOT IN
(SELECT Seq3.Seq
FROM Sequence Seq2
INNER JOIN Sequence Seq3
ON Seq3.Seq > Seq2.Seq
WHERE Seq2.Seq < @MaxCheck
AND Seq2.Seq <> 1
AND Seq3.Seq%Seq2.Seq = 0)
AND Seq <> 1 --remove 1 as it is not prime
ORDER BY Seq

Must do some work now... :-)

Subject: Prime Numbers
Posted by: parody (view profile)
Posted on: Friday, July 31, 2009 at 9:14 AM
Message: Along the avoiding checking we dont need to do it helps scalability to remove those we know are not prime to start with also. Apologies for all the posts!

DELETE FROM Sequence
WHERE Seq NOT IN
(SELECT 6*Seq+1 AS Seq
FROM Sequence)
AND Seq NOT IN
(SELECT 6*Seq-1 AS Seq
FROM Sequence)

DECLARE @MaxCheck tinyint
SET @MaxCheck = (SELECT SQRT(MAX(Seq)) FROM Sequence)

SELECT 2 As Seq
UNION
SELECT 3 As Seq
UNION
SELECT Seq FROM Sequence Seq1
WHERE Seq NOT IN
(SELECT Seq3.Seq
FROM Sequence Seq2
INNER JOIN Sequence Seq3
ON Seq3.Seq > Seq2.Seq
WHERE Seq2.Seq < @MaxCheck
AND Seq2.Seq <> 1
AND Seq3.Seq%Seq2.Seq = 0)
AND Seq <> 1 --remove 1 as it is not prime
ORDER BY Seq

Subject: Prime Numbers
Posted by: parody (view profile)
Posted on: Friday, July 31, 2009 at 9:16 AM
Message: oops dont need the
AND Seq <> 1 --remove 1 as it is not prime
anymore...

Subject: Prime Numbers
Posted by: parody (view profile)
Posted on: Friday, July 31, 2009 at 9:45 AM
Message: Final version, found the culprit for the performance. This is much more scalable now, even if you dont remove the non primes first.

--Remove non primes
DELETE FROM Sequence
WHERE Seq NOT IN
(SELECT 6*Seq+1 AS Seq
FROM Sequence)
AND Seq NOT IN
(SELECT 6*Seq-1 AS Seq
FROM Sequence)

--Find max number to bother checking
DECLARE @MaxCheck int
SET @MaxCheck = (SELECT CEILING(SQRT(MAX(Seq))) FROM Sequence)

--Get primes
SELECT 2 As Seq
UNION
SELECT 3 As Seq
UNION
SELECT Seq FROM Sequence Seq1
WHERE Seq NOT IN
(SELECT Seq3.Seq
FROM Sequence Seq2
INNER JOIN Sequence Seq3
ON Seq3.Seq > Seq2.Seq
WHERE Seq2.Seq BETWEEN 2 AND @MaxCheck
AND Seq3.Seq%Seq2.Seq = 0)
ORDER BY Seq

Subject: Prime Numbers
Posted by: parody (view profile)
Posted on: Friday, July 31, 2009 at 11:04 AM
Message: Just tested my final solution above scaling up to finding 664579 primes in a 10,000,000 sequence table in 4m59s including the delete. 78498 Primes in 1,000,000 table in 36s. 9592 in 100,000 in 1s.

I think it is one of the faster solutions for its simplicity.

Subject: Portability?
Posted by: Peso (not signed in)
Posted on: Sunday, August 02, 2009 at 4:33 PM
Message: DECLARE @MaxPrime INT

SET @MaxPrime = 10000

;WITH h0 (Value)
AS (
SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL
SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL
SELECT 8 UNION ALL SELECT 9 UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL
SELECT 12 UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL SELECT 15
), h1 (Value)
AS (
SELECT 0 UNION ALL SELECT 16 UNION ALL SELECT 32 UNION ALL SELECT 48 UNION ALL
SELECT 64 UNION ALL SELECT 80 UNION ALL SELECT 96 UNION ALL SELECT 112 UNION ALL
SELECT 128 UNION ALL SELECT 144 UNION ALL SELECT 160 UNION ALL SELECT 176 UNION ALL
SELECT 192 UNION ALL SELECT 208 UNION ALL SELECT 224 UNION ALL SELECT 240
), h2 (Value)
AS (
SELECT 0 UNION ALL SELECT 256 UNION ALL SELECT 512 UNION ALL SELECT 768 UNION ALL
SELECT 1024 UNION ALL SELECT 1280 UNION ALL SELECT 1536
), Candidates (Value)
AS (
SELECT 6 * h2.Value + 6 * h1.Value + 6 * h0.Value + 5
FROM h0
INNER JOIN h1 ON h1.Value <= @MaxPrime
INNER JOIN h2 ON h2.Value <= @MaxPrime
WHERE 6 * h2.Value + 6 * h1.Value + 6 * h0.Value + 5 <= @MaxPrime
AND (6 * h2.Value + 6 * h1.Value + 6 * h0.Value + 5) % 10 IN (1, 3, 7, 9)

UNION ALL

SELECT 6 * h2.Value + 6 * h1.Value + 6 * h0.Value + 7
FROM h0
INNER JOIN h1 ON h1.Value <= @MaxPrime
INNER JOIN h2 ON h2.Value <= @MaxPrime
WHERE 6 * h2.Value + 6 * h1.Value + 6 * h0.Value + 7 <= @MaxPrime
AND (6 * h2.Value + 6 * h1.Value + 6 * h0.Value + 7) % 10 IN (1, 3, 7, 9)
), Yak (Prime)
AS (
SELECT k
FROM (
SELECT 2 AS k UNION ALL
SELECT 3 UNION ALL SELECT 5
) AS d
WHERE k <= @MaxPrime

UNION ALL

SELECT c.Value
FROM Candidates AS c
WHERE NOT EXISTS (SELECT * FROM Candidates AS p WHERE p.Value <= SQRT(@MaxPrime) AND c.Value > p.Value AND c.Value % p.Value = 0)
AND c.Value <= @MaxPrime
)

SELECT Prime
FROM Yak

Subject: C# CLR version
Posted by: Anonymous (not signed in)
Posted on: Monday, August 03, 2009 at 9:24 AM
Message: Not quite in the spirit of pure SQL but this CLR function does the trick:

[Microsoft.SqlServer.Server.SqlFunction]
public static bool IsPrime(int i_number)
{
bool b_return = true;
for (int i = 2; i < (i_number / 2) + 1; i++)
{
if ((i_number % i) == 0)
{
b_return = false;
break;
}
}
return b_return;
}

Subject: No Sequence Table Needed
Posted by: solaco (view profile)
Posted on: Monday, August 03, 2009 at 3:13 PM
Message: How about this?

set nocount on
declare @numbers int, @divisors int, @divisorsCount int
declare @PrimeNumbers table (PrimeNumber int)
set @numbers = 1
while @numbers <= 1000
begin
set @divisors=1
set @divisorsCount=0
while @divisors<=@numbers
begin
if @numbers % @divisors = 0
set @divisorsCount=@divisorsCount+1

set @divisors=@divisors+1

if @divisorsCount > 2
break
end

if @divisorsCount<3
insert @PrimeNumbers values(@numbers)

set @numbers=@numbers+1
end

select * from @PrimeNumbers

Subject: slight improve for ANSWER #1
Posted by: Lythom (not signed in)
Posted on: Tuesday, August 04, 2009 at 4:53 AM
Message: At the end of ANSWER #1, Joe Celko use the condition :
<code style="font-size: 12px;"><span style="color:blue">WHERE </span><span style="color:black">P1.p </span><span style="color:gray"><= </span><span style="color:magenta">CEILING </span><span style="color:gray">(</span><span style="color:magenta">SQRT </span><span style="color:gray">(</span><span style="color:black">Primes.p</span><span style="color:gray">))</span></code>

Remember that a>b <=> a*a>b*b, a>0, b>0. When comparing integers square root, it is quicker to multiply one than using sqrt function on the other which cost a lot.In this case, it is better to transform the condition into :
<code style="font-size: 12px;"><span style="color:blue">WHERE </span><span style="color:black">P1.p</span><span style="color:gray">*</span><span style="color:black">P1.p </span><span style="color:gray"><= </span><span style="color:black">Primes.p<br></span></code>

This tip can be applied in any algorithm in any language and is really quicker.

Subject: This must be wrong; it looks too simple, once more with feeling...
Posted by: Lee (view profile)
Posted on: Monday, August 10, 2009 at 4:07 PM
Message: I see I should have included 1 in the answer set. Oh well. Don't know where I got the idea that it should not have been included. I actually had to go out of my way to omit it. If it's not too late, here it is:

INSERT INTO Primes (p)
SELECT s1.seq
FROM Sequence s1
WHERE NOT EXISTS (SELECT 1
FROM Sequence s2
WHERE s2.seq BETWEEN 2
AND SQRT (s1.seq)
AND s1.seq % s2.seq = 0)

Subject: 1 is not Prime
Posted by: parody (view profile)
Posted on: Wednesday, August 12, 2009 at 3:22 AM
Message: according to wikipedia

http://en.wikipedia.org/wiki/Prime_number#Primality_of_one

Subject: Prime Numbers (plain DB2) - improved performance
Posted by: lkhiger (view profile)
Posted on: Sunday, September 06, 2009 at 5:14 PM
Message: with
limit (lim) as
(select int(100000) from sysibm.sysdummy1
)
,
numbers (num) as
(select 2 from sysibm.sysdummy1
union all
select num + 1 from numbers, limit
where num + 1 <= int(sqrt(lim)) + 1
)
,
prime_check (prime_num, prime_ind) as
(select int(2), varchar('P', 1) from sysibm.sysdummy1
union all
select 3, 'P' from sysibm.sysdummy1
union all
select prime_num + 2,
case
when int(substr(digits(prime_num + 2), 10, 1)) = 5 and prime_num + 2 > 5 then 'R'
when
mod(
int(substr(digits(prime_num + 2 ), 1, 1)) + int(substr(digits(prime_num + 2 ), 2, 1)) +
int(substr(digits(prime_num + 2 ), 3, 1)) + int(substr(digits(prime_num + 2 ), 4, 1)) +
int(substr(digits(prime_num + 2 ), 5, 1)) + int(substr(digits(prime_num + 2 ), 6, 1)) +
int(substr(digits(prime_num + 2 ), 7, 1)) + int(substr(digits(prime_num + 2 ), 8, 1)) +
int(substr(digits(prime_num + 2 ), 9, 1)) + int(substr(digits(prime_num + 2 ), 10, 1)), 3) = 0
and prime_num + 2 > 3
then 'R'
when
mod(
int(substr(digits(prime_num + 2 ), 1, 1)) - int(substr(digits(prime_num + 2 ), 2, 1)) +
int(substr(digits(prime_num + 2 ), 3, 1)) - int(substr(digits(prime_num + 2 ), 4, 1)) +
int(substr(digits(prime_num + 2 ), 5, 1)) - int(substr(digits(prime_num + 2 ), 6, 1)) +
int(substr(digits(prime_num + 2 ), 7, 1)) - int(substr(digits(prime_num + 2 ), 8, 1)) +
int(substr(digits(prime_num + 2 ), 9, 1)) - int(substr(digits(prime_num + 2 ), 10, 1)), 11) = 0
and prime_num + 2 > 11
then 'R'

when
1 = (select 1 from sysibm.sysdummy1
where exists
(select 1 from numbers
where
num <= int(sqrt(prime_num)) + 1
and mod(prime_num + 2, num) = 0 ) )
then 'R' else 'P'
end
from prime_check, limit
where
prime_num + 2 <= int(sqrt(lim)) + 1
)
,
prime_num_1 (prime_num) as
(select prime_num from prime_check
where prime_ind = 'P'
)
,
prime_check_2 (prime_num, prime_ind) as
(select max(prime_num), varchar('X', 1)
from prime_num_1
union all
select p2.prime_num + 2,
case
when int(substr(digits(p2.prime_num + 2), 10, 1)) = 5 then 'R'
when
mod(
int(substr(digits(p2.prime_num + 2 ), 1, 1)) + int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
int(substr(digits(p2.prime_num + 2 ), 3, 1)) + int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
int(substr(digits(p2.prime_num + 2 ), 5, 1)) + int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
int(substr(digits(p2.prime_num + 2 ), 7, 1)) + int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
int(substr(digits(p2.prime_num + 2 ), 9, 1)) + int(substr(digits(p2.prime_num + 2 ), 10, 1)), 3) = 0
then 'R'
when
mod(
6 * int(substr(digits(p2.prime_num + 2 ), 1, 1)) + 2 * int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
3 * int(substr(digits(p2.prime_num + 2 ), 3, 1)) + 1 * int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
5 * int(substr(digits(p2.prime_num + 2 ), 5, 1)) + 4 * int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
6 * int(substr(digits(p2.prime_num + 2 ), 7, 1)) + 2 * int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
3 * int(substr(digits(p2.prime_num + 2 ), 9, 1)) + 1 * int(substr(digits(p2.prime_num + 2 ), 10, 1)), 7) = 0
then 'R' when
mod(
int(substr(digits(p2.prime_num + 2 ), 1, 1)) - int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
int(substr(digits(p2.prime_num + 2 ), 3, 1)) - int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
int(substr(digits(p2.prime_num + 2 ), 5, 1)) - int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
int(substr(digits(p2.prime_num + 2 ), 7, 1)) - int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
int(substr(digits(p2.prime_num + 2 ), 9, 1)) - int(substr(digits(p2.prime_num + 2 ), 10, 1)), 11) = 0
then 'R'
when
1 = (select 1 from sysibm.sysdummy1
where exists
(select 1 from prime_num_1 p1
where
p1.prime_num <= int(sqrt(p2.prime_num)) + 1
and mod(p2.prime_num + 2, p1.prime_num) = 0 ) )
then 'R' else 'P'
end
from prime_check_2 p2, limit lm
where
p2.prime_num + 2 <= lim
)
,
prime_number (prime_num) as
(select * from prime_num_1
union all
select prime_num from prime_check_2
where prime_ind = 'P'
)
select
prime_num "Prime Number"
from prime_number

Subject: So who won?
Posted by: Lee (view profile)
Posted on: Tuesday, October 20, 2009 at 10:26 AM
Message: If a winner was announced, I didn't see it.

Subject: In interval [1, 1000000] we found 78498 prime numbers in 1 minute (DB2):
Posted by: lkhiger (view profile)
Posted on: Saturday, November 07, 2009 at 12:49 PM
Message: with lim(lim) as(select 1000000 from sysibm.sysdummy1),prime1(prime, K) as(select int(2), 0 from sysibm.sysdummy1 union allselect (2 * (K + 1) + 1), K + 1 from prime1, lim where K + 1 < lim / 2 ) ,prime_fact(prime) as(select p1.prime from(select prime from prime1, lim where prime <= sqrt(lim) ) p1left join (select prime from prime1, lim where prime <= sqrt(lim) ) p2On mod(p1.prime, p2.prime) = 0 and p2.prime <= sqrt(p1.prime)Where p2.prime is null) select prime from prime_factunion allselect prime from prime1 p1, lim where p1.prime > sqrt(lim)and not exists(select 1 from prime_fact f1 where mod(p1.prime, f1.prime) = 0 and f1.prime <= sqrt(p1.prime) )

Subject: In interval [1, 1000000] we found 78498 prime numbers in 1 minute (DB2):
Posted by: lkhiger (view profile)
Posted on: Saturday, November 07, 2009 at 12:54 PM
Message: [code]with lim(lim) as
(select 1000000 from sysibm.sysdummy1
)
,
prime1(prime, K) as
(select int(2), 0 from sysibm.sysdummy1

union all

select (2 * (K + 1) + 1), K + 1
from prime1, lim
where K + 1 < lim / 2
)
,
prime_fact(prime) as
(select p1.prime
from
(select prime
from prime1, lim
where prime <= sqrt(lim) ) p1

left join

(select prime
from prime1, lim
where prime <= sqrt(lim) ) p2
On

mod(p1.prime, p2.prime) = 0
and p2.prime <= sqrt(p1.prime)

Where p2.prime is null
)

select prime from prime_fact

union all

select prime from prime1 p1, lim

where p1.prime > sqrt(lim)
and not exists
(select 1 from prime_fact f1
where mod(p1.prime, f1.prime) = 0
and f1.prime <= sqrt(p1.prime) )[/code]

Subject: so, who won?
Posted by: Brian from Chicago (view profile)
Posted on: Thursday, January 31, 2013 at 8:04 PM
Message: ?

Subject: This is about as easy and fast as possible, set-based
Posted by: Peso (view profile)
Posted on: Sunday, March 17, 2013 at 1:03 AM
Message: CREATE TABLE #Numbers
(
PrimeCandidate INT NOT NULL,
Squared BIGINT PRIMARY KEY CLUSTERED
);

DECLARE @MaxPrime INT = 1000000;

WITH n0(p)
AS (
SELECT 1

UNION ALL

SELECT 1
), n1(p)
AS (
SELECT 1
FROM n0 AS a
CROSS JOIN n0 AS b
), n2(p)
AS (
SELECT 1
FROM n1 AS a
CROSS JOIN n1 AS b
), n3(p)
AS (
SELECT 1
FROM n2 AS a
CROSS JOIN n2 AS b
), n4(p)
AS (
SELECT 1
FROM n3 AS a
CROSS JOIN n3 AS b
), n5(p)
AS (
SELECT 1
FROM n4 AS a
CROSS JOIN n4 AS b
)
INSERT #Numbers
(
PrimeCandidate,
Squared
)
SELECT f.PrimeCandidate,
f.PrimeCandidate * f.PrimeCandidate AS Squared
FROM (
SELECT TOP (1 + @MaxPrime / 30)
30 * ROW_NUMBER() OVER (ORDER BY p)
FROM n5
) AS v(Value)
CROSS APPLY (
VALUES (v.Value - 23),
(v.Value - 19),
(v.Value - 17),
(v.Value - 13),
(v.Value - 11),
(v.Value - 7),
(v.Value - 1),
(v.Value + 1)
) AS f(PrimeCandidate)
WHERE f.PrimeCandidate <= @MaxPrime;

SELECT Prime
FROM (
VALUES (2),
(3),
(5)
) AS v(Prime)
WHERE Prime <= @MaxPrime

UNION ALL

SELECT n.PrimeCandidate
FROM #Numbers AS n
WHERE NOT EXISTS (
SELECT *
FROM #Numbers AS p
WHERE p.Squared <= n.PrimeCandidate
AND n.PrimeCandidate % p.PrimeCandidate = 0
);

DROP TABLE #Numbers;

 

Phil Factor
Searching for Strings in SQL Server Databases

Sometimes, you just want to do a search in a SQL Server database as if you were using a search engine like Google.... Read more...

 View the blog

Top Rated

SQL Server XML Questions You Were Too Shy To Ask
 Sometimes, XML seems a bewildering convention that offers solutions to problems that the average... Read more...

Continuous Delivery and the Database
 Continuous Delivery is fairly generally understood to be an effective way of tackling the problems of... Read more...

The SQL Server Sqlio Utility
 If, before deployment, you need to push the limits of your disk subsystem in order to determine whether... Read more...

The PoSh DBA - Reading and Filtering Errors
 DBAs regularly need to keep an eye on the error logs of all their SQL Servers, and the event logs of... Read more...

MySQL Compare: The Manual That Time Forgot, Part 1
 Although SQL Compare, for SQL Server, is one of Red Gate's best-known products, there are also 'sister'... Read more...

Most Viewed

Beginning SQL Server 2005 Reporting Services Part 1
 Steve Joubert begins an in-depth tour of SQL Server 2005 Reporting Services with a step-by-step guide... Read more...

Ten Common Database Design Mistakes
 If database design is done right, then the development, deployment and subsequent performance in... Read more...

SQL Server Index Basics
 Given the fundamental importance of indexes in databases, it always comes as a surprise how often the... Read more...

Reading and Writing Files in SQL Server using T-SQL
 SQL Server provides several "standard" techniques by which to read and write to files but, just... Read more...

Concatenating Row Values in Transact-SQL
 It is an interesting problem in Transact SQL, for which there are a number of solutions and... Read more...

Why Join

Over 400,000 Microsoft professionals subscribe to the Simple-Talk technical journal. Join today, it's fast, simple, free and secure.