9 Replies Latest reply: Oct 4, 2012 2:12 AM by jeneesh RSS

    how to retrive prime numbers from a Number column using only SQL Query

    563005
      Hi all,

      Can any one help me in writing a SQL Query.I have a column which is of number type
      and have a data of 1 - 100 numbers.Is there any way in which I can retrive prime numbers using a SQL Query only and not from PL/SQL Program.

      Thanks in Advance.
      Don.
        • 1. Re: how to retrive prime numbers from a Number column using only SQL Query
          Rob van Wijk
          SQL> select l prime_number
            2    from (select level l from dual connect by level <= 100)
            3       , (select level m from dual connect by level <= 100)
            4   where m<=l
            5   group by l
            6  having count(case l/m when trunc(l/m) then 'Y' end) = 2
            7   order by l
            8  /

                                    PRIME_NUMBER
          --------------------------------------
                                               2
                                               3
                                               5
                                               7
                                              11
                                              13
                                              17
                                              19
                                              23
                                              29
                                              31
                                              37
                                              41
                                              43
                                              47
                                              53
                                              59
                                              61
                                              67
                                              71
                                              73
                                              79
                                              83
                                              89
                                              97

          25 rijen zijn geselecteerd.
          Regards,
          Rob.
          • 2. Re: how to retrive prime numbers from a Number column using only SQL Query
            563005
            Hi Rob,

            Thanks for the early reply, But pls, can u explain me clearly step-by-step , as I am new to SQL It's a bit difficult for me to understand.

            Tx,
            Don.
            • 3. Re: how to retrive prime numbers from a Number column using only SQL Query
              Rob van Wijk
              But pls, can u explain me clearly step-by-step , as I am new to SQL
                1  select l prime_number
                2    from (select level l from dual connect by level <= 100)
                3       , (select level m from dual connect by level <= 100)
                4   where m<=l
                5   group by l
                6  having count(case l/m when trunc(l/m) then 'Y' end) = 2
                7   order by l
              Sure, line 2 and 3 are both generating the numbers 1 until 100. Without a where clause they would give 10,000 rows, having all combinations of two numbers between 1 and 100.

              The next step is to filter out the rows where m>l. After this step you have the pairs (1,1), (2,1), (2,2), (3,1), (3,2), (3,3), (4,1) et cetera. You will have 5,050 rows left at this stage.

              Line 5 is grouping by the l column, to have 100 records again. The prime number check is in the having clause at line 6. You divide the l number by the m number and only when it can be divided ( l/m = trunc(l/m) ), you are counting. Prime numbers are the ones that have two m numbers (1 and the number l itself), so only those are displayed.

              Hope this helps.

              Regards,
              Rob.
              • 4. Re: how to retrive prime numbers from a Number column using only SQL Query
                563005
                Hi Rob,

                Thanks a lot. it is really helpful.Once again thankq for your early reply and explanation.

                Tx,
                Don.
                • 5. Re: how to retrive prime numbers from a Number column using only SQL Query
                  572471
                  Here's another solution by using model clause in 10g.
                  With algorithm, described in
                  http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
                  we can find all the prime numbers by writing such a query:
                  SQL> with t as (select level l from dual connect by level <= 100)
                    2  --
                    3  SELECT l prim_num FROM
                    4     (select * from t
                    5       model
                    6        dimension by (l dim)
                    7        measures (l,2 temp)
                    8         rules iterate (1000000) until (power(temp[1],2)>100)
                    9           (l[DIM>TEMP[1]]=decode(mod(l[CV()],temp[1]),0,null,l[CV()]),
                  10            temp[1]=min(l)[dim>temp[1]])
                  11     )
                  12  WHERE l IS NOT NULL
                  13  /

                    PRIM_NUM
                  ----------
                           1
                           2
                           3
                           5
                           7
                          11
                          13
                          17
                          19
                          23
                          29
                          31
                          37
                          41
                          43
                          47
                          53
                          59
                          61
                          67
                          71
                          73
                          79
                          83
                          89
                          97

                  26 rows selected

                  SQL>
                  and it's quicker than a cartesian join given by Rob.
                  • 7. Re: how to retrive prime numbers from a Number column using only SQL Query
                    Satyaki_De
                    Excellent... Really, refresh my mind.

                    Regards.

                    Satyaki De.
                    • 8. Re: how to retrive prime numbers from a Number column using only SQL Query
                      558634
                      Another solution, too simple to explain in words:

                      Select level as n From dual Connect By level < 101
                      Minus
                      Select n1.n * n2.n
                      From
                      (Select level as n From dual Where Level >1 Connect By level < 51) n1,
                      (Select level as n From dual Where Level >1 Connect By level < 51) n2
                      • 9. Re: how to retrive prime numbers from a Number column using only SQL Query
                        jeneesh
                        user555631 wrote:
                        Another solution, too simple to explain in words:

                        Select level as n From dual Connect By level < 101
                        Minus
                        Select n1.n * n2.n
                        From
                        (Select level as n From dual Where Level >1 Connect By level < 51) n1,
                        (Select level as n From dual Where Level >1 Connect By level < 51) n2
                        Welcome to the forum..

                        It took 5 years for you to find out this...!

                        Please dont reply to very old thread..