How to print prime numbers within given range

I have been trying to write a logic to print all prime numbers.

And it works as expected till range of 1 to 100.

But when I increase the range it dose not work from 1 to 500

Can some explain in details what is wrong in my below code and how it can be improved.

Any easy or different way to print prime numbers will be much appreciated

Code :

SELECT
    result
FROM
    (
        SELECT
            CASE
                WHEN ROWNUM = 2 THEN
                    ROWNUM
                WHEN ROWNUM = 3 THEN
                    ROWNUM
                WHEN ROWNUM = 5 THEN
                    ROWNUM
            END AS result
        FROM
            dual
        CONNECT BY
            ROWNUM <= 5
    )
WHERE
    result IS NOT NULL
UNION ALL
SELECT
    result
FROM
    (
        SELECT
            decr1 AS result
        FROM
            (
                SELECT
                    rn AS decr1
                FROM
                    (
                        SELECT
                            ROWNUM AS rn
                        FROM
                            dual
                        CONNECT BY
                            ROWNUM < 1000
                    )
            )
        WHERE
            decr1 > 5
        MINUS
        SELECT
            decr AS result
        FROM
            (
                SELECT
                    t.rn AS decr
                FROM
                    (
                        SELECT
                            ROWNUM AS rn
                        FROM
                            dual
                        CONNECT BY
                            ROWNUM < 1000
                    ) t
                WHERE
                    rn >= 6
            )
        WHERE
            mod(decr, 2) = 0
            OR mod(decr, 3) = 0
            OR mod(decr, 4) = 0
            OR mod(decr, 5) = 0
            OR mod(decr, 6) = 0
            OR mod(decr, 7) = 0
            OR mod(decr, 8) = 0
            OR mod(decr, 9) = 0
            OR mod(decr, 10) = 0
    );

My output for range of 1 to 100

CodePudding user response：

You've thrown out processing efficiency when you decided to do this in SQL, so you might as well go for something that is clear. Here is a SQL that is pretty much straight along the lines of the definition of a prime number:

with nat as (SELECT rownum n FROM DUAL CONNECT BY ROWNUM <= 100 )
SELECT n   -- give me any number...
from   nat n1  -- ... from the set of natural numbers ...
where   not exists ( SELECT n FROM nat n2 where mod(n1.n,n2.n)=0 AND n2.n between 2 and n1.n-1)  -- ... that cannot be evenly divided by a smaller natural number
and n > 1  -- ... and 1 is not prime

CodePudding user response：

select num prime_number
from (select level num from dual connect by level <= 500 ),
 (select level denom from dual connect by level <= 500 )
where denom<=num
group by num
having count(case num/denom when trunc(num/denom) then 'Y' end) = 2
order by num

Using Oracle's connect, we can generate our set of numerators and denominators. Then we can filter any denominators greater than the numerator (no point in dividing 2 by 3, etc). Finally, the having clause will return the prime numbers.

Fiddle The first query in the fiddle kind of shows what is going on, the second one is gives you your primes.

CodePudding user response：

A positive integer is prime if it is strictly greater than 1, and if it is not divisible by any positive integers besides 1 and the number itself. To check for primality, it is enough to know if the number is divisible by a number between 2 and trunc(sqrt(that_number)). In code:

with
  user_input (n) as (
    select :n              -- user input goes here
    from   dual
  )
, candidates (p) as (
    select  level
    from    user_input 
    where   level > 1
    connect by level <= n
  )
, prep (f) as (
    select  level
    from    dual
    where   level > 1
    connect by level <= trunc(sqrt(:n))
  )
select p as prime
from   candidates
where  not exists (
                    select f
                    from   prep
                    where  f <= trunc(sqrt(p))
                           and
                           mod(p, f) = 0
                  )
;

The input (at the top of the query, in the with clause) is a bind variable, you can set it to 100 or whatever you need.

NOTE: This will be quite slow if you need all the primes up to 100,000 for example (it takes 2.3 seconds on my machine). Don't even try up to 1 million or more. For those, you need a better algorithm. We all learned the Erathostenes' sieve algorithm in primary school; that is trivial to code in a procedural language (like PL/SQL), not so easy in a declarative language (like SQL - proving that "declarative" is just a marketing word, and perhaps an ideal, but not a reality). For a pretty long discussion see https://community.oracle.com/tech/developers/discussion/3931268/sql-puzzle-prime-numbers/p1 which was rendered hard to read by Oracle's change of forum platform provider a few years back.

CodePudding user response：

Adjust the CONNECT by value if you want more or less values


select a output
    from (select level a from dual connect by level <= 500),
         (select level b from dual connect by level <= 500)
    where b<=a
    group by a
    having count(case a/b when trunc(a/b) then 'Y' end) = 2
    order by a;

CodePudding user response：

You can use use a row-generator to generate all the values and then use CROSS JOIN LATERAL to check if each value is prime:

SELECT prime
FROM   (
         SELECT LEVEL   1 AS prime
         FROM   DUAL
         CONNECT BY LEVEL < 100
       ) p
       CROSS JOIN LATERAL (
         SELECT 1
         FROM   DUAL
         WHERE  MOD(prime, level) = 0
         CONNECT BY LEVEL * LEVEL <= prime
         HAVING COUNT(*) = 1
       )

Which outputs:

PRIME

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

PRIME
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

fiddle