23 July 2009

Celko’s Summer SQL Stumpers: Prime Numbers

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 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:

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.

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

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. 

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

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. 

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. 

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.

ANSWER #3

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

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.  

Keep up to date with Simple-Talk

For more articles like this delivered fortnightly, sign up to the Simple-Talk newsletter

Downloads

This post has been viewed 17842 times – thanks for reading.

Tags: , , ,

  • Rate
    [Total: 15    Average: 3.9/5]
  • Share

Joe Celko

View all articles by Joe Celko

  • Phil Factor

    Primes under 10,000

    –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

  • Matthew

    Isn’t 3 a prime
    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.

  • Jonathan Kehayias

    Another quick method

    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

  • Theo Spears

    An ugly solution
    –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

  • Leonid_Khiger_at_Citigroup

    Prime numbers (plain DB2)
    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)

  • karthi_sql2005@yahoo.co.in

    (6 * n ± 1) formula
    Can’t we use any other number here?

  • Jason Miller

    I must be doing something wrong…
    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

  • Tamás Hajdu

    defense of the 6n+-1 formula
    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)

  • Matt

    Use the webservice
    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.

  • Leonid_Khiger_at_Citigroup

    Prime numbers (plain DB2) — 2
    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.

  • Absinthe

    Brute force? But were we supposed to avoid the "WHILE"?
    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

  • Brian V

    My attempt (19 secs for 1-10000)

    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

  • dgrace

    How I handled it
    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

  • Adam Haines

    My Solution
    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.

  • Jason Miller

    I think I figured out the issue
    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.)

  • Matt

    good for small, not as scalable as it could be
    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

  • MikeD

    primes to 1 million
    /*
    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)

  • brandonh6k

    Sieve in TSQL
    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

  • Absinthe

    Brute force? But were we supposed to avoid the “WHILE”?
    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

  • Lee

    This must be wrong; it looks too simple
    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)

  • Lee

    This must be wrong; it looks too simple, con’t.
    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.

  • Anonymous

    Brute force improved
    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

  • Jonathan Kehayias

    Another quick method
    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

  • Peso

    Sieve Of Atkin implementation
    /*
    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

  • parody

    Prime Numbers
    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

  • parody

    Prime Numbers
    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

  • parody

    Prime Numbers
    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

  • parody

    Prime Numbers
    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… 🙂

  • parody

    Prime Numbers
    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… 🙂

  • parody

    Prime Numbers
    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

  • parody

    Prime Numbers
    oops dont need the
    AND Seq <> 1 –remove 1 as it is not prime
    anymore…

  • parody

    Prime Numbers
    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

  • parody

    Prime Numbers
    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.

  • Peso

    Portability?
    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

  • Anonymous

    C# CLR version
    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;
    }

  • solaco

    No Sequence Table Needed
    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

  • Lythom

    slight improve for ANSWER #1
    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.

  • Lee

    This must be wrong; it looks too simple, once more with feeling…
    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)

  • parody

    1 is not Prime
    according to wikipedia

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

  • lkhiger

    Prime Numbers (plain DB2) – improved performance
    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

  • Lee

    So who won?
    If a winner was announced, I didn’t see it.

  • lkhiger

    In interval [1, 1000000] we found 78498 prime numbers in 1 minute (DB2):
    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) )

  • lkhiger

    In interval [1, 1000000] we found 78498 prime numbers in 1 minute (DB2):
    [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]

  • Brian from Chicago

    so, who won?
    ?

  • Peso

    This is about as easy and fast as possible, set-based
    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;

  • simon155

    Prime
    Bearing in mind sql is far more efficient at set operations, wouldn’t the below (apart from being simpler) be faster than a multiple-loop approach? On an old dev machine, 19 seconds for all prime under 1 million, retained under the assumption someone wants to keep them…

    create table prime (primeno bigint)
    declare @counter bigint
    set @counter = 2
    while @counter < 1000000
    begin
    if not exists(select top 1 primeno from prime where @counter % primeno = 0 )
    insert into prime select @counter
    set @counter = @counter + 1
    end
    select * from prime order by 1

  • simon155

    Prime (Notes)
    I’m aware that logically speaking your mod operations could be reduced significantly ie divide target by lowest prime (2), and cap your max prime to check as target / 2. Divide by next lowest prime (3) and cap max prime to check as target / 3 etc.. Not spent much time looking at this, but at a glance SQL seems faster doing the code above than a "logical programmatic approach".

  • simon155

    *note
    Disclaimer: This assumes you don’t already have a seq table in place to avoid the loop requirement etc

  • simon155

    Prime – More readable
    These dont get compared or checked – Verified by no one calling me on the entry above! 🙂

    The CTE method is the most efficient. If you find it hard to read though, you might want to try a small revision. Code follows

    IF (SELECT OBJECT_ID (‘tempdb.dbo.#Numbers’)) IS NOT NULL
    DROP TABLE #Numbers;

    CREATE TABLE #Numbers (Prime INT NOT NULL, Squared BIGINT PRIMARY KEY CLUSTERED);

    DECLARE @MaxPrime INT = 1000000;

    ;WITH
    GroupingDriver AS
    (
    SELECT CAST(‘7’ AS BIGINT) as Interval
    UNION ALL
    SELECT Interval+30
    FROM GroupingDriver
    WHERE Interval+30 < @MaxPrime
    )
    INSERT INTO #Numbers
    SELECT 2 AS ‘Number’, 4 AS ‘SquareNo’
    UNION ALL
    SELECT 3 AS ‘Number’, 9 AS ‘SquareNo’
    UNION ALL
    SELECT 5 AS ‘Number’, 25 AS ‘SquareNo’
    UNION ALL
    SELECT Prime.Number, Prime.Number * Prime.Number
    FROM GroupingDriver
    CROSS APPLY ( VALUES (GroupingDriver.Interval), (GroupingDriver.Interval+4), (GroupingDriver.Interval+6), (GroupingDriver.Interval+10), (GroupingDriver.Interval+12), (GroupingDriver.Interval+16), (GroupingDriver.Interval+22), (GroupingDriver.Interval+24) ) AS Prime(Number)
    WHERE Prime.Number < @MaxPrime
    OPTION (MAXRECURSION 0);

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