# Thread: Prime numbers (plain DB2)

1. Registered User
Join Date
Jul 2009
Location
NY
Posts
963

## Unanswered: Prime numbers (plain DB2)

In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. The first twenty-five prime numbers are:

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

To find prime numbers we'll use the theorem:
If for number N not exists divisor 1 < k <= Sqrt(N) then N is the prime.

Base on this theorem we'll create the DB2 query:

Code:
with
limit (lim) as
(select int(10000) from sysibm.sysdummy1
)
,
numbers (num) as
(select 2 from sysibm.sysdummy1
union all
select num + 1 from numbers, limit
where num + 1 <= int(sqrt(lim)) + 1
)
,
prime_nbr(prime_num, prime_ind) as
(select int(2), varchar('P', 1) from sysibm.sysdummy1
union all
select 3, 'P' from sysibm.sysdummy1
union all
select prime_num + 2, 'P'
from prime_nbr, limit
where
prime_num + 2 <= lim
and
not exists
(select 1 from numbers
where num <= int(sqrt(prime_num )) + 1
and
prime_num + 2 = int((prime_num + 2) / num) * num )
union all
select prime_num + 2, 'R'
from prime_nbr, limit
where
prime_num + 2 <= lim
and
exists
(select 1 from numbers
where num <= int(sqrt(prime_num )) + 1
and
prime_num + 2 = int((prime_num + 2) / num) * num )
)
select prime_num "prime number" from prime_nbr
where prime_ind = 'P'
You will spend just 2 seconds to get all primes from 2 to 10000.

You will get 1229 primes in RS. No formula exists for prime number, but computerization can help us in many problems.

Lenny K.
Last edited by sathyaram_s; 07-23-09 at 10:53. Reason: changed quote tag to code tag

2. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
Changing lim in the limit table you can get the different sets of prime numbers.

Lenny K.

3. Registered User
Join Date
Jul 2006
Location
Pune , India
Posts
433
my try... not able to pick 2,3 though

with temp(no) as (select row_number() over() from syscat.columns fetch first 100 rows only ),
temp2(no ,remainder) as (select t1.no , mod(t1.no , t2.no) from temp t1 , temp t2
where t2.no <= sqrt (t1.no) and t2.no <> 1
)
select no from temp2 group by no having no* min(remainder) <> 0

4. Registered User
Join Date
Jul 2006
Location
Pune , India
Posts
433
this will complete:

select no from (values (2),(3) ) as t(no) where no in (select no from temp)
union
select no from temp2 group by no having no* min(remainder) <> 0

5. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
Thanks for reply. I don't have v9, yet.

Lenny

6. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
The next step, as usual is simplification and optimization of the basic query:

with
limit (lim) as
(select int(10000) from sysibm.sysdummy1
)
,
numbers (num) as
(select 2 from sysibm.sysdummy1
union all
select num + 1 from numbers, limit
where num + 1 <= int(sqrt(lim)) + 1
)
,
prime_check (prime_num, prime_ind) as
(select int(2), varchar('P', 1) from sysibm.sysdummy1
union all
select 3, 'P' from sysibm.sysdummy1
union all
select prime_num + 2,
case
when
1 = (select 1 from sysibm.sysdummy1
where
exists
(select 1 from numbers
where num <= int(sqrt(prime_num )) + 1
and
prime_num + 2 = int((prime_num + 2) / num) * num ) )
then 'R'
else 'P'
end
from prime_check, limit
where
prime_num + 2 <= lim
)
,
prime_num_1 (prime_num) as
(select prime_num from prime_check
where prime_ind = 'P'
)
select prime_num "prime number" from prime_num_1

Lenny K.

7. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
The complete query which is optimized (basic query get first 1,000,000
primary numbers in more then 1 hours. The last one in 5 minutes):

with
limit (lim) as
(select int(100000) from sysibm.sysdummy1
)
,
numbers (num) as
(select 2 from sysibm.sysdummy1
union all
select num + 1 from numbers, limit
where num + 1 <= int(sqrt(lim)) + 1
)
,
prime_check (prime_num, prime_ind) as
(select int(2), varchar('P', 1) from sysibm.sysdummy1
union all
select 3, 'P' from sysibm.sysdummy1
union all
select prime_num + 2,
case
when
1 = (select 1 from sysibm.sysdummy1
where
exists
(select 1 from numbers
where num <= int(sqrt(prime_num)) + 1
and
prime_num + 2 = int((prime_num + 2) / num) * num ) )
then 'R'
else 'P'
end
from prime_check, limit
where
prime_num + 2 <= int(sqrt(lim)) + 1
)
,
prime_num_1 (prime_num) as
(select prime_num from prime_check
where prime_ind = 'P'
)
,
prime_check_2 (prime_num, prime_ind) as
(select max(prime_num), varchar('X', 1)
from prime_num_1
union all
select p2.prime_num + 2,
case
when
1 = (select 1 from sysibm.sysdummy1
where exists
(select 1 from prime_num_1 p1
where p1.prime_num <= int(sqrt(p2.prime_num)) + 1
and
p2.prime_num + 2= int((p2.prime_num + 2) / p1.prime_num ) * p1.prime_num ) )
then 'R'
else 'P'
end
from prime_check_2 p2, limit lm
where
p2.prime_num + 2 <= lim
)
,
prime_number (prime_num) as
(select * from prime_num_1
union All
select prime_num from prime_check_2
where prime_ind = 'P'
)
select prime_num "Prime Number"
from prime_number
Lenny K.
Last edited by Lenny77; 07-24-09 at 14:45.

8. Registered User
Join Date
Jul 2009
Posts
150
Maybe is good idea to replace:
prime_num + 2 = int((prime_num + 2) / num) * num ) )
with
0 = mode(prime_num + 2, num) ?
Last edited by DB2Plus; 07-25-09 at 13:32.

9. SQL Consultant
Join Date
Apr 2002
Location
Posts
20,002
hey lenny check this out -- Celko's Summer SQL Stumpers: Prime Numbers

you should enter the contest

don't forget the last point: 5) Explain how you got your answer.

10. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
Originally Posted by r937
hey lenny check this out -- Celko's Summer SQL Stumpers: Prime Numbers

you should enter the contest

don't forget the last point: 5) Explain how you got your answer.

Thank you for link. I did it.

Lenny.

11. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
Thank you, DB2Plus.

I replaced the equaty num = p * (num / p) by mod(num, p) = 0.

It's not improve the performance, but looks more compact:

with
limit (lim) as
(select int(100000) from sysibm.sysdummy1
)
,
numbers (num) as
(select 2 from sysibm.sysdummy1
union all
select num + 1 from numbers, limit
where num + 1 <= int(sqrt(lim)) + 1
)
,
prime_check (prime_num, prime_ind) as
(select int(2), varchar('P', 1) from sysibm.sysdummy1
union all
select 3, 'P' from sysibm.sysdummy1
union all
select prime_num + 2,
case
when
1 = (select 1 from sysibm.sysdummy1
where exists
(select 1 from numbers
where
num <= int(sqrt(prime_num)) + 1
and mod(prime_num + 2, num) = 0 ) )
then 'R' else 'P'
end
from prime_check, limit
where
prime_num + 2 <= int(sqrt(lim)) + 1
)
,
prime_num_1 (prime_num) as
(select prime_num from prime_check
where prime_ind = 'P'
)
,
prime_check_2 (prime_num, prime_ind) as
(select max(prime_num), varchar('X', 1)
from prime_num_1
union all
select p2.prime_num + 2,
case
when
1 = (select 1 from sysibm.sysdummy1
where exists
(select 1 from prime_num_1 p1
where
p1.prime_num <= int(sqrt(p2.prime_num)) + 1
and mod(p2.prime_num + 2, p1.prime_num) = 0 ) )
then 'R' else 'P'
end
from prime_check_2 p2, limit lm
where
p2.prime_num + 2 <= lim
)
,
prime_number (prime_num) as
(select * from prime_num_1
union all
select prime_num from prime_check_2
where prime_ind = 'P'
)
select prime_num "Prime Number"
from prime_number
Lenny K.

12. Registered User
Join Date
Jul 2006
Location
Pune , India
Posts
433
Originally Posted by Lenny77
Thanks for reply. I don't have v9, yet.

Lenny
?? which function is not compatible with v8 luw (i can see article from 2004 describing row_number() over() :
Using DB2 UDB OLAP functions
)
are you on z-os ?

13. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
Originally Posted by rahul_s80
?? which function is not compatible with v8 luw (i can see article from 2004 describing row_number() over() :
Using DB2 UDB OLAP functions
)
are you on z-os ?
I am working on OS390.

Anyway, thanks. I understood what you mean.

14. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
Using some simple divisibility rules we can improve performance of the query in times !

with
limit (lim) as
(select int(100000) from sysibm.sysdummy1
)
,
numbers (num) as
(select 2 from sysibm.sysdummy1
union all
select num + 1 from numbers, limit
where num + 1 <= int(sqrt(lim)) + 1
)
,
prime_check (prime_num, prime_ind) as
(select int(2), varchar('P', 1) from sysibm.sysdummy1
union all
select 3, 'P' from sysibm.sysdummy1
union all
select prime_num + 2,
case
when
1 = (select 1 from sysibm.sysdummy1
where exists
(select 1 from numbers
where
num <= int(sqrt(prime_num)) + 1
and mod(prime_num + 2, num) = 0 ) )
then 'R' else 'P'
end
from prime_check, limit
where
prime_num + 2 <= int(sqrt(lim)) + 1
)
,
prime_num_1 (prime_num) as
(select prime_num from prime_check
where prime_ind = 'P'
)
,
prime_check_2 (prime_num, prime_ind) as
(select max(prime_num), varchar('X', 1)
from prime_num_1
union all
select p2.prime_num + 2,
case
when int(substr(digits(p2.prime_num + 2), 10, 1)) = 5 then 'R'
when
mod(
int(substr(digits(p2.prime_num + 2 ), 1, 1)) + int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
int(substr(digits(p2.prime_num + 2 ), 3, 1)) + int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
int(substr(digits(p2.prime_num + 2 ), 5, 1)) + int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
int(substr(digits(p2.prime_num + 2 ), 7, 1)) + int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
int(substr(digits(p2.prime_num + 2 ), 9, 1)) + int(substr(digits(p2.prime_num + 2 ), 10, 1)), 3) = 0
then 'R'
when
mod(
int(substr(digits(p2.prime_num + 2 ), 1, 1)) - int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
int(substr(digits(p2.prime_num + 2 ), 3, 1)) - int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
int(substr(digits(p2.prime_num + 2 ), 5, 1)) - int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
int(substr(digits(p2.prime_num + 2 ), 7, 1)) - int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
int(substr(digits(p2.prime_num + 2 ), 9, 1)) - int(substr(digits(p2.prime_num + 2 ), 10, 1)), 11) = 0
then 'R'
when
1 = (select 1 from sysibm.sysdummy1
where exists
(select 1 from prime_num_1 p1
where
p1.prime_num <= int(sqrt(p2.prime_num)) + 1
and mod(p2.prime_num + 2, p1.prime_num) = 0 ) )
then 'R' else 'P'
end
from prime_check_2 p2, limit lm
where
p2.prime_num + 2 <= lim
)
,
prime_number (prime_num) as
(select * from prime_num_1
union all
select prime_num from prime_check_2
where prime_ind = 'P'
)
select prime_num "Prime Number"
from prime_number
Lenny
Last edited by Lenny77; 08-28-09 at 15:19.

15. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
Finally, we can add some divisibility rules by 7. It will optimize our query, too.

with
limit (lim) as
(select int(1000000) from sysibm.sysdummy1
)
,
numbers (num) as
(select 2 from sysibm.sysdummy1
union all
select num + 1 from numbers, limit
where num + 1 <= int(sqrt(lim)) + 1
)
,
prime_check (prime_num, prime_ind) as
(select int(2), varchar('P', 1) from sysibm.sysdummy1
union all
select 3, 'P' from sysibm.sysdummy1
union all
select prime_num + 2,
case
when int(substr(digits(prime_num + 2), 10, 1)) = 5 and prime_num + 2 > 5 then 'R'
when
mod(
int(substr(digits(prime_num + 2 ), 1, 1)) + int(substr(digits(prime_num + 2 ), 2, 1)) +
int(substr(digits(prime_num + 2 ), 3, 1)) + int(substr(digits(prime_num + 2 ), 4, 1)) +
int(substr(digits(prime_num + 2 ), 5, 1)) + int(substr(digits(prime_num + 2 ), 6, 1)) +
int(substr(digits(prime_num + 2 ), 7, 1)) + int(substr(digits(prime_num + 2 ), 8, 1)) +
int(substr(digits(prime_num + 2 ), 9, 1)) + int(substr(digits(prime_num + 2 ), 10, 1)), 3) = 0
and prime_num + 2 > 3
then 'R'
when
mod(
int(substr(digits(prime_num + 2 ), 1, 1)) - int(substr(digits(prime_num + 2 ), 2, 1)) +
int(substr(digits(prime_num + 2 ), 3, 1)) - int(substr(digits(prime_num + 2 ), 4, 1)) +
int(substr(digits(prime_num + 2 ), 5, 1)) - int(substr(digits(prime_num + 2 ), 6, 1)) +
int(substr(digits(prime_num + 2 ), 7, 1)) - int(substr(digits(prime_num + 2 ), 8, 1)) +
int(substr(digits(prime_num + 2 ), 9, 1)) - int(substr(digits(prime_num + 2 ), 10, 1)), 11) = 0
and prime_num + 2 > 11
then 'R'

when
1 = (select 1 from sysibm.sysdummy1
where exists
(select 1 from numbers
where
num <= int(sqrt(prime_num)) + 1
and mod(prime_num + 2, num) = 0 ) )
then 'R' else 'P'
end
from prime_check, limit
where
prime_num + 2 <= int(sqrt(lim)) + 1
)
,
prime_num_1 (prime_num) as
(select prime_num from prime_check
where prime_ind = 'P'
)
,
prime_check_2 (prime_num, prime_ind) as
(select max(prime_num), varchar('X', 1)
from prime_num_1
union all
select p2.prime_num + 2,
case
when int(substr(digits(p2.prime_num + 2), 10, 1)) = 5 then 'R'
when
mod(
int(substr(digits(p2.prime_num + 2 ), 1, 1)) + int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
int(substr(digits(p2.prime_num + 2 ), 3, 1)) + int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
int(substr(digits(p2.prime_num + 2 ), 5, 1)) + int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
int(substr(digits(p2.prime_num + 2 ), 7, 1)) + int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
int(substr(digits(p2.prime_num + 2 ), 9, 1)) + int(substr(digits(p2.prime_num + 2 ), 10, 1)), 3) = 0
then 'R'
when
mod(
6 * int(substr(digits(p2.prime_num + 2 ), 1, 1)) + 2 * int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
3 * int(substr(digits(p2.prime_num + 2 ), 3, 1)) + 1 * int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
5 * int(substr(digits(p2.prime_num + 2 ), 5, 1)) + 4 * int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
6 * int(substr(digits(p2.prime_num + 2 ), 7, 1)) + 2 * int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
3 * int(substr(digits(p2.prime_num + 2 ), 9, 1)) + 1 * int(substr(digits(p2.prime_num + 2 ), 10, 1)), 7) = 0
then 'R'
when
mod(
int(substr(digits(p2.prime_num + 2 ), 1, 1)) - int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
int(substr(digits(p2.prime_num + 2 ), 3, 1)) - int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
int(substr(digits(p2.prime_num + 2 ), 5, 1)) - int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
int(substr(digits(p2.prime_num + 2 ), 7, 1)) - int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
int(substr(digits(p2.prime_num + 2 ), 9, 1)) - int(substr(digits(p2.prime_num + 2 ), 10, 1)), 11) = 0
then 'R'
when
1 = (select 1 from sysibm.sysdummy1
where exists
(select 1 from prime_num_1 p1
where
p1.prime_num <= int(sqrt(p2.prime_num)) + 1
and mod(p2.prime_num + 2, p1.prime_num) = 0 ) )
then 'R' else 'P'
end
from prime_check_2 p2, limit lm
where
p2.prime_num + 2 <= lim
)
,
prime_number (prime_num) as
(select * from prime_num_1
union all
select prime_num from prime_check_2
where prime_ind = 'P'
)
select prime_num "Prime Number"
from prime_number
Lenny

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•