Portal | Manuals | References | Downloads | Info | Programs | JCLs | Master the Mainframes
IBM Mainframe Computers Forums Index
 
Register
 
IBM Mainframe Computers Forums Index Mainframe: Search IBM Mainframe Forum: FAQ Memberlist Usergroups Profile Log in to check your private messages Log in
 

 

Prime numbers (plain DB2)

 
Post new topic   Reply to topic    IBMMAINFRAMES.com Support Forums -> DB2
View previous topic :: :: View next topic  
Author Message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Fri Sep 04, 2009 4:29 pm    Post subject: Prime numbers (plain DB2)
Reply with quote

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

You have to know: Doesn't exist any formula for prime numbers.

But DB2 is so powerful that allow us to find the prime numbers in one statement.
Just change LIM in the following SQL and you'll get all prime numbers between 2 and LIM.

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


Ask me, if you have a questions.
You can copy and execute this SQL in DB2 version 8 and up.


Sincerely, Lenny Khiger icon_idea.gif icon_idea.gif icon_idea.gif
Back to top
View user's profile Send private message

lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Sat Sep 05, 2009 4:46 am    Post subject: Prime Factorization
Reply with quote

How you can expecting for Prime Factorization of number we have to use the result of the previous SQL....

But this is not TRUE.

We don't need to use the set of the prime number explicitly:

Code:
with number (number) as
(select int(2009) from sysibm.sysdummy1)
,
factors(fact) as
(select 2 from sysibm.sysdummy1
union all
select fact + 1
from factors, number
where fact + 1 <= number
)
,
Prime_Factorization (in_number, remd, Prime_Factorization) as
(select number, number, varchar('1', 1000)
from number
union all
select in_number, int(remd / fact), Prime_Factorization || ' * ' || varchar(fact)
from Prime_Factorization, factors
where mod(remd, fact) = 0 and remd > 1
and fact = (select min(fact) from factors where mod(remd, fact) = 0 )
)
select in_number "Number", Prime_Factorization "Prime Factorization of number"
from Prime_Factorization
where remd = 1


Lenny icon_rolleyes.gif icon_rolleyes.gif icon_rolleyes.gif
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Sat Sep 05, 2009 5:16 am    Post subject:
Reply with quote

To understand how is difficult the problem of Prime Factorization try to do it by yourself for number 2009 (see example) using paper and pen (only).... icon_neutral.gif icon_neutral.gif icon_neutral.gif

In code you can change the NUMBER (in sample 2009) by your number.

Lenny icon_lol.gif icon_lol.gif icon_lol.gif
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Sat Sep 12, 2009 8:26 pm    Post subject: Greatest common divisor (gcd, or GCD)
Reply with quote

Next problem which I suppose to solve in this topic will be:
calculation of Greatest common divisor....

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf) or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

For example, gcd(42, 56) = 14....

My algorithm will not use solution for the Prime Number and Prime Factorization as well. icon_idea.gif icon_idea.gif icon_idea.gif

Lenny
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Sat Sep 12, 2009 10:54 pm    Post subject: Algorithm for calculation GCD
Reply with quote

Algorithm:

We'll not use nor multiplication, nor division.
Substraction only we'll use for calculation of GCD.

For example calculation GCD(56, 42)

Step1: RemD = 42, GCD = 56
Step2:
GCD =max(GCD, RemD - GCD) = max(42, 56 - 42) = 42,
RemD =min(GCD, RemD - GCD) = min(42, 56 - 42) = 14

All next steps using the logics of the Step2

Step3: RemD = 14, GCD = 28

Loop until RemD > 0 icon_exclaim.gif icon_exclaim.gif icon_exclaim.gif

Step4: RemD = 14, GCD = 14
Step5: RemD = 0, GCD = 14

Calculation finished: GCD = 14

You can create SQL, using this algorithm. icon_cool.gif

Thanks, Lenny
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Tue Sep 15, 2009 7:20 am    Post subject: Greatest common divisor
Reply with quote

How I promissed:

Code:
with
Input  (Num1, Num2) as
(select int(42), int(56) from sysibm.sysdummy1
)
,
GCD_calc(Remd, GCD) as
(select max(Num1, Num2), min(Num1, Num2)
   from Input
Union All
select max(Remd - GCD, GCD), min(Remd - GCD, GCD)
  from GCD_calc
  where max(Remd - GCD, GCD) > min(Remd - GCD, GCD) 
    and GCD > 1 
)
select Num1, Num2, GCD "Greatest common divisor"
from Input,
(select GCD from GCD_calc
  where remd = (select min(remd) from GCD_calc)) cc 


Result:

Quote:
NUM1 NUM2 Greatest common divisor
42 ....... 56 ........ 14


Lenny
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Sun Sep 20, 2009 4:34 am    Post subject: Short formula for prime numbers
Reply with quote

Short formula for prime numbers

I have created also the short formula to get prime numbers.

But performance of big one is much better.

I use this formula for small numbers, or to check is number prime.

Code:

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
)
select num "Prime Number"
   from numbers n1
where n1.num =
(select min(cand)
   from
   (select  min(n2.num) cand
      from numbers n2
     where mod(n1.num, n2.num) = 0
       and  n2.num <= sqrt(n1.num) + 1
    Union All
    select  n1.num cand
      from sysibm.sysdummy1  ) ii
)


Lenny
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Sun Sep 20, 2009 5:05 am    Post subject: Fixing the short formula
Reply with quote

icon_arrow.gif Correction to the short formula:

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 <= lim
)

select num "Prime Number"
   from numbers n1
where n1.num =
(select min(cand)
   from
   (select  min(n2.num) cand
      from numbers n2
     where mod(n1.num, n2.num) = 0
       and  n2.num <= sqrt(n1.num) + 1
    Union All
    select  n1.num cand
      from sysibm.sysdummy1  ) ii )


Lenny
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Sun Sep 20, 2009 8:49 am    Post subject: Optimization of the short formula
Reply with quote

How you understood only 2 could be prime number (not odd), so we can easily change the formula and improve performance of it twice:


Code:
With
limit (lim) as
(select int(10000) from sysibm.sysdummy1
)
,
numbers (num) as
(select 2 from sysibm.sysdummy1
union all
select 3 from sysibm.sysdummy1
union all
select num + 2 from numbers, limit
where num + 2 <= lim + 1
)

select num "Prime Number"
   from numbers n1
where n1.num =
(select min(cand)
   from
   (select  min(n2.num) cand
      from numbers n2
     where mod(n1.num, n2.num) = 0
       and  n2.num <= sqrt(n1.num) + 1
    Union All
    select  n1.num cand
      from sysibm.sysdummy1  ) ii )


Lenny icon_idea.gif icon_idea.gif icon_exclaim.gif
Back to top
View user's profile Send private message
lkhiger

New User


Joined: 28 Oct 2005
Posts: 89

PostPosted: Sun Sep 20, 2009 7:14 pm    Post subject: Getting primes within interval
Reply with quote

If you have to find all prime numbers in interval [M1, M2]
where M1 <= M2 <= Lim you can use following query:


Code:
With
limit (lim) as
(select int(10000) from sysibm.sysdummy1
)
,
numbers (num) as
(select 2 from sysibm.sysdummy1
union all
select 3 from sysibm.sysdummy1
union all
select num + 2 from numbers, limit
where num + 2 <= lim + 1
)

select num "Prime Number"
   from numbers n1
where
n1.num between M1 and M2
and n1.num =
(select min(cand)
   from
   (select  min(n2.num) cand
      from numbers n2
     where mod(n1.num, n2.num) = 0
       and  n2.num <= sqrt(n1.num) + 1
    Union All
    select  n1.num cand
      from sysibm.sysdummy1  ) ii )


Lenny
Back to top
View user's profile Send private message
View previous topic :: :: View next topic  
Post new topic   Reply to topic    IBMMAINFRAMES.com Support Forums -> DB2 All times are GMT + 6 Hours
Page 1 of 1

 

Search our Forum:

Similar Topics
Topic Author Forum Replies Posted
No new posts Incorrect output when trying to add n... monica1 PL/I & Assembler 10 Fri Jan 13, 2017 5:02 pm
No new posts Row-Numbers of distinct rows? Auryn DB2 1 Thu Oct 20, 2016 4:38 pm
No new posts comparing comp-3 and unpacked numbers juares castro COBOL Programming 3 Mon May 30, 2016 6:46 pm
No new posts Sort Trick for numbers pshongal DFSORT/ICETOOL 4 Tue Mar 22, 2016 1:33 pm
No new posts Display the exponential numbers in no... bipinpeter CLIST & REXX 4 Tue Jan 19, 2016 6:28 pm


Facebook
Back to Top
 
Mainframe Wiki | Forum Rules | Bookmarks | Subscriptions | FAQ | Tutorials | Contact Us