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 [message #684671] Thu, 22 July 2021 11:36 Go to next message
saipradyumn
Messages: 408
Registered: October 2011
Location: Hyderabad
Senior Member
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 Go to previous messageGo to next message
Michel Cadot
Messages: 68006
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account 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 Go to previous messageGo to next message
saipradyumn
Messages: 408
Registered: October 2011
Location: Hyderabad
Senior Member


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 Go to previous message
Michel Cadot
Messages: 68006
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account 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: Mon Oct 25 05:40:37 CDT 2021