Prime

I took my son to see the Transformers movie this weekend — one of the main characters is Optimus Prime, or “Prime” for short.

This post is tangentially related to a challenge by Howard Rogers on whether or not one can come up with a use case for the SCOTT.EMP table which cannot be solved using plain SQL but that requires PL/SQL.  You can read about it here.

Personally I’m not so sure there is such a use case, since any set transformation should be able to be specified by using any set of sets.  And today using the connect by level tricks, one can arbitrarily construct any set one likes and use that to apply any transformation.  Heck, it’s probably mathematically provable, but just thinking about it starts to give me flashbacks and headaches…

In any case, one of my suggestions to this problem involves calculating prime numbers — it’s not a solution to the problem, because it’s possible to use SQL to generate prime numbers, but it’s an interesting problem just the same.  A long time ago, I wrote a prime number generator in APL — it’s really easy there (single line of “code”, actually), but I bet it would be neat to see how to do it in SQL.

So, my “quiz” today is:

Using only SQL, generate a list of the first 100 prime numbers.

10 Responses to “Prime”

  1. Raj Jamadagni Says:

    trying to repost since the comment ate most of what I wrote.

    wrote this fairly quickly. The logic is thus,

    1. take a number a,
    2. take a number b such that b is between 1 and sqrt(a)
    3. calculate m = mod(a,b)
    4. select all values of a where all values of m are greater than 0.

    WITH x AS (SELECT ROWNUM+1 r FROM all_objects WHERE ROWNUM

  2. ddelmoli Says:

    Looks like it’s still being eaten… But the logic appears sound to me.

  3. Raj Jamadagni Says:


    wrote this fairly quickly. The logic is thus,

    1. take a number a,
    2. take a number b such that b is between 1 and sqrt(a)
    3. calculate m = mod(a,b) for each value of b
    4. select all values of a where all values of m are greater than 0.

    WITH x AS (SELECT ROWNUM+1 r FROM all_objects WHERE ROWNUM < 1001)
    SELECT n
    , SUM (CASE WHEN m = 0 THEN 1 ELSE 0 END) m_0
    FROM (SELECT a.r n, mod (a.r, b.r) m
    FROM x a, x b
    WHERE b.r <= sqrt(a.r)
    ORDER BY 1, 2)
    GROUP BY n
    HAVING SUM (CASE WHEN m = 0 THEN 1 ELSE 0 END) = 0
    ORDER BY 1

    Please note, this doesn't technically solve the query since it misses 2 and 3 but feel free to take a hack at it.

  4. chris Says:

    I think the above solution doesn’t fulfill the requirement to produce 100 primes. Here’s my sql:

    with nr_lines as (
    select 100 nr_lines
    from dual)
    ,test_limit as (
    select 1000 test_limit
    from dual)
    ,nr as (
    select level+1 nr
    from test_limit
    connect by level

  5. chris Says:

    with nr_lines as (
    select 100 nr_lines
    from dual)
    ,test_limit as (
    select 1000 test_limit
    from dual)
    ,nr as (
    select level+1 nr
    from test_limit
    connect by level

  6. chris Says:

    This is annoying. I’m giving up.

  7. Raj Jamadagni Says:

    Chris, mail it to Dominic. That’s what i did to get it posted correctly.

    Raj

  8. Andre Says:

    –this one has no less than signs, so it should be safe to post, I hope

    with N as (select level+1 n from dual connect by rownum between 1 and 541)
    select n from n minus select a.n * b.n from n a, n b

  9. Kurt Says:

    A very performant query, for larger lists.
    When a divisor is found for te current number, the query stops checking the other potential divisors up to the sqrt.
    You can reject the AND “(MOD(g.getal,ROWNUM-1) > 0 OR ROWNUM 0 OR ROWNUM 1;

  10. Ritesh Singh Says:

    Please visit this article
    http://www.oracledba.in/display_article.aspx?article_id=287#ReviewId

Leave a Reply

Posting code can be a pain. To make sure your code doesn't get eaten, you may want to pre-format it first by using HTML Encoder