9 Replies Latest reply: Oct 4, 2012 2:12 AM by jeneesh

# how to retrive prime numbers from a Number column using only SQL Query

Hi all,

Can any one help me in writing a SQL Query.I have a column which is of number type
and have a data of 1 - 100 numbers.Is there any way in which I can retrive prime numbers using a SQL Query only and not from PL/SQL Program.

Don.
• ###### 1. Re: how to retrive prime numbers from a Number column using only SQL Query
```SQL> select l prime_number
2    from (select level l from dual connect by level <= 100)
3       , (select level m from dual connect by level <= 100)
4   where m<=l
5   group by l
6  having count(case l/m when trunc(l/m) then 'Y' end) = 2
7   order by l
8  /

PRIME_NUMBER
--------------------------------------
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

25 rijen zijn geselecteerd.```
Regards,
Rob.
• ###### 2. Re: how to retrive prime numbers from a Number column using only SQL Query
Hi Rob,

Thanks for the early reply, But pls, can u explain me clearly step-by-step , as I am new to SQL It's a bit difficult for me to understand.

Tx,
Don.
• ###### 3. Re: how to retrive prime numbers from a Number column using only SQL Query
But pls, can u explain me clearly step-by-step , as I am new to SQL
```  1  select l prime_number
2    from (select level l from dual connect by level <= 100)
3       , (select level m from dual connect by level <= 100)
4   where m<=l
5   group by l
6  having count(case l/m when trunc(l/m) then 'Y' end) = 2
7   order by l```
Sure, line 2 and 3 are both generating the numbers 1 until 100. Without a where clause they would give 10,000 rows, having all combinations of two numbers between 1 and 100.

The next step is to filter out the rows where m>l. After this step you have the pairs (1,1), (2,1), (2,2), (3,1), (3,2), (3,3), (4,1) et cetera. You will have 5,050 rows left at this stage.

Line 5 is grouping by the l column, to have 100 records again. The prime number check is in the having clause at line 6. You divide the l number by the m number and only when it can be divided ( l/m = trunc(l/m) ), you are counting. Prime numbers are the ones that have two m numbers (1 and the number l itself), so only those are displayed.

Hope this helps.

Regards,
Rob.
• ###### 4. Re: how to retrive prime numbers from a Number column using only SQL Query
Hi Rob,

Tx,
Don.
• ###### 5. Re: how to retrive prime numbers from a Number column using only SQL Query
Here's another solution by using model clause in 10g.
With algorithm, described in
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
we can find all the prime numbers by writing such a query:
```SQL> with t as (select level l from dual connect by level <= 100)
2  --
3  SELECT l prim_num FROM
4     (select * from t
5       model
6        dimension by (l dim)
7        measures (l,2 temp)
8         rules iterate (1000000) until (power(temp[1],2)>100)
9           (l[DIM>TEMP[1]]=decode(mod(l[CV()],temp[1]),0,null,l[CV()]),
10            temp[1]=min(l)[dim>temp[1]])
11     )
12  WHERE l IS NOT NULL
13  /

PRIM_NUM
----------
1
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

26 rows selected

SQL> ```
and it's quicker than a cartesian join given by Rob.
• ###### 6. Re: how to retrive prime numbers from a Number column using only SQL Query
Splendid!
• ###### 7. Re: how to retrive prime numbers from a Number column using only SQL Query
Excellent... Really, refresh my mind.

Regards.

Satyaki De.
• ###### 8. Re: how to retrive prime numbers from a Number column using only SQL Query
Another solution, too simple to explain in words:

Select level as n From dual Connect By level < 101
Minus
Select n1.n * n2.n
From
(Select level as n From dual Where Level >1 Connect By level < 51) n1,
(Select level as n From dual Where Level >1 Connect By level < 51) n2
• ###### 9. Re: how to retrive prime numbers from a Number column using only SQL Query
user555631 wrote:
Another solution, too simple to explain in words:

Select level as n From dual Connect By level < 101
Minus
Select n1.n * n2.n
From
(Select level as n From dual Where Level >1 Connect By level < 51) n1,
(Select level as n From dual Where Level >1 Connect By level < 51) n2
Welcome to the forum..

It took 5 years for you to find out this...!