Prime Generation Logic using in single Query [message #684671] |
Thu, 22 July 2021 11:36 |
|
saipradyumn
Messages: 419 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 |
|
Michel Cadot
Messages: 68665 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 #684676 is a reply to message #684674] |
Thu, 22 July 2021 14:13 |
|
Michel Cadot
Messages: 68665 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
|
|
|