Portal | Manuals | References | Downloads | Info | Programs | JCLs | Mainframe wiki | Quick Ref

Author Message
lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

Posted: Fri Sep 04, 2009 4:29 pm    Post subject: 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....

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

lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

Posted: Sat Sep 05, 2009 4:46 am    Post subject: Prime Factorization

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
lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

 Posted: Sat Sep 05, 2009 5:16 am    Post subject: 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).... In code you can change the NUMBER (in sample 2009) by your number. Lenny
lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

 Posted: Sat Sep 12, 2009 8:26 pm    Post subject: Greatest common divisor (gcd, or GCD) 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. Lenny
lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

 Posted: Sat Sep 12, 2009 10:54 pm    Post subject: Algorithm for calculation GCD 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 Step4: RemD = 14, GCD = 14 Step5: RemD = 0, GCD = 14 Calculation finished: GCD = 14 You can create SQL, using this algorithm. Thanks, Lenny
lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

Posted: Tue Sep 15, 2009 7:20 am    Post subject: Greatest common divisor

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
lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

Posted: Sun Sep 20, 2009 4:34 am    Post subject: Short formula for prime numbers

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
lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

Posted: Sun Sep 20, 2009 5:05 am    Post subject: Fixing the short formula

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
lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

Posted: Sun Sep 20, 2009 8:49 am    Post subject: Optimization of the short formula

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
lkhiger

New User

Joined: 28 Oct 2005
Posts: 89

Posted: Sun Sep 20, 2009 7:14 pm    Post subject: Getting primes within interval

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
 All times are GMT + 6 Hours
 Page 1 of 1

Search our Forum:

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

 © 2003-2017 IBM MAINFRAME Software Support Division
 Job Vacancies | Forum Rules | Bookmarks | Subscriptions | FAQ | Polls | Contact Us