Home » SQL & PL/SQL » SQL & PL/SQL » Prime Generation Logic using in single Query (Oracle Database 11g Enterprise Edition Release 11.2.0.4.0 - 64bit Production)
Prime Generation Logic using in single Query Thu, 22 July 2021 11:36
I am trying to generate the prime numbers with in the given range by using single query. But unable to iterate the second loop.

Able to find out weather number is prime or not with the help of single query

```
WITH DATA AS (SELECT 13, LEVEL+1 , MOD(13, LEVEL+1) REMAIN  FROM DUAL CONNECT BY LEVEL  <13-1)
select  CASE WHEN COUNT(DECODE(REMAIN,0,1)) =0 THEN  'PRIME -'||13 ELSE ' NOT PRIME - ' ||13 END  CNT  FROM DATA D;

```

To generate the prime numbers my idea was : After generating the required range, need to iterate the each and every number to get remainder

``` WITH NUMBERS AS  ( SELECT  17+LEVEL-1  RANGE_NUM FROM DUAL CONNECT BY LEVEL < (20-17))
SELECT RANGE_NUM, LEVEL+1 , MOD(RANGE_NUM, LEVEL+1) REMAIN  FROM NUMBERS  CONNECT BY LEVEL  <RANGE_NUM-1  ;
```
But its not working as I expected .

Please provide some thoughts to achieve this

Re: Prime Generation Logic using in single Query [message #684673 is a reply to message #684671] Thu, 22 July 2021 11:52
 Michel Cadot Messages: 68043Registered: March 2007 Location: Nanterre, France, http://... Senior MemberAccount Moderator

Using CONNECT BY will lead quickly to infinite response time and/or exceeded memory error when numbers increase.
Here's a very old query giving the prime numbers between two numbers (written in the past millennium, just for fun and small numbers):
```with t as ( select level+1 id from dual connect by level < 2*&High )
select id "Prime Nb"
from t t1
where not exists ( select 1 from t t2
where mod(t1.id, t2.id) = 0
and t2.id > 1
and t2.id < ceil(t1.id/2)+1
)
and t1.id >= &Low
and t1.id <= &High
/```

[Updated on: Thu, 22 July 2021 13:56]

Report message to a moderator

Re: Prime Generation Logic using in single Query [message #684674 is a reply to message #684673] Thu, 22 July 2021 12:38

thank you very much for your inputs
Re: Prime Generation Logic using in single Query [message #684676 is a reply to message #684674] Thu, 22 July 2021 14:13
 Michel Cadot Messages: 68043Registered: March 2007 Location: Nanterre, France, http://... Senior MemberAccount Moderator

If you are interested in prime numbers, the first efficient algorithm was the sieve of Eratosthenes (3rd cent. BCE) but the modern age really starts with sieve of Sundaram (1934). The best algorithm I know is the sieve of Atkin (2003).
I implemented and optimized them in PL/SQL to compare, here are the results on my laptop.
```Compute the prime numbers less than 1,000,000:
getPrimesSQL         : Elapsed: 117h 08mn 48.01s (the above query)
getPrimesEratosthene : Elapsed:  00h 00mn 09.25s
getPrimesSundaram    : Elapsed:  00h 00mn 00.45s
getPrimesAtkin       : Elapsed:  00h 00mn 00.37s```
```Compute the 4O,000,000th prime number (776,531,401):
getPrimeEratosthene  : Elapsed: 42h 30mn 51.29s
getPrimeSundaram     : Elapsed: 05h 51mn 26.92s
getPrimeAtkin        : Elapsed: 00h 05mn 11.60s```
I was flabbergasted at the results the first time I saw the efficiency of the latest algorithms.
For those who are interested, here's a link to the article where the Altkin algorithm was first described:
https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf

[Updated on: Thu, 22 July 2021 14:17]

Report message to a moderator

 Previous Topic: Statement Level trigger - After Insert/Update Next Topic: Execution Plan of query
Goto Forum:

Current Time: Thu Dec 02 13:23:02 CST 2021