Prime
July 26th, 2007 — ddelmoliI took my son to see the Transformers movie this weekend — one of the main characters is Optimus Prime, or “Prime” for short.
This post is tangentially related to a challenge by Howard Rogers on whether or not one can come up with a use case for the SCOTT.EMP table which cannot be solved using plain SQL but that requires PL/SQL. You can read about it here.
Personally I’m not so sure there is such a use case, since any set transformation should be able to be specified by using any set of sets. And today using the connect by level tricks, one can arbitrarily construct any set one likes and use that to apply any transformation. Heck, it’s probably mathematically provable, but just thinking about it starts to give me flashbacks and headaches…
In any case, one of my suggestions to this problem involves calculating prime numbers — it’s not a solution to the problem, because it’s possible to use SQL to generate prime numbers, but it’s an interesting problem just the same. A long time ago, I wrote a prime number generator in APL — it’s really easy there (single line of “code”, actually), but I bet it would be neat to see how to do it in SQL.
So, my “quiz” today is:
Using only SQL, generate a list of the first 100 prime numbers.
July 26th, 2007 at 1:44 pm
trying to repost since the comment ate most of what I wrote.
wrote this fairly quickly. The logic is thus,
1. take a number a,
2. take a number b such that b is between 1 and sqrt(a)
3. calculate m = mod(a,b)
4. select all values of a where all values of m are greater than 0.
WITH x AS (SELECT ROWNUM+1 r FROM all_objects WHERE ROWNUM
July 26th, 2007 at 2:09 pm
Looks like it’s still being eaten… But the logic appears sound to me.
July 26th, 2007 at 2:22 pm
wrote this fairly quickly. The logic is thus,
1. take a number a,
2. take a number b such that b is between 1 and sqrt(a)
3. calculate m = mod(a,b) for each value of b
4. select all values of a where all values of m are greater than 0.
WITH x AS (SELECT ROWNUM+1 r FROM all_objects WHERE ROWNUM < 1001)
SELECT n
, SUM (CASE WHEN m = 0 THEN 1 ELSE 0 END) m_0
FROM (SELECT a.r n, mod (a.r, b.r) m
FROM x a, x b
WHERE b.r <= sqrt(a.r)
ORDER BY 1, 2)
GROUP BY n
HAVING SUM (CASE WHEN m = 0 THEN 1 ELSE 0 END) = 0
ORDER BY 1
Please note, this doesn't technically solve the query since it misses 2 and 3 but feel free to take a hack at it.
July 27th, 2007 at 9:39 am
I think the above solution doesn’t fulfill the requirement to produce 100 primes. Here’s my sql:
with nr_lines as (
select 100 nr_lines
from dual)
,test_limit as (
select 1000 test_limit
from dual)
,nr as (
select level+1 nr
from test_limit
connect by level
July 27th, 2007 at 9:45 am
with nr_lines as (
select 100 nr_lines
from dual)
,test_limit as (
select 1000 test_limit
from dual)
,nr as (
select level+1 nr
from test_limit
connect by level
July 27th, 2007 at 9:45 am
This is annoying. I’m giving up.
July 27th, 2007 at 1:37 pm
Chris, mail it to Dominic. That’s what i did to get it posted correctly.
Raj
July 27th, 2007 at 5:01 pm
–this one has no less than signs, so it should be safe to post, I hope
with N as (select level+1 n from dual connect by rownum between 1 and 541)
select n from n minus select a.n * b.n from n a, n b
January 10th, 2008 at 3:33 am
A very performant query, for larger lists.
When a divisor is found for te current number, the query stops checking the other potential divisors up to the sqrt.
You can reject the AND “(MOD(g.getal,ROWNUM-1) > 0 OR ROWNUM 0 OR ROWNUM 1;