[lennykhiger]

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:

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

[lennykhiger]

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:

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

[lennykhiger]

Thanks to everybody who will try to execute my queries and let me know how they work.

Lenny

[lennykhiger]

The greatest common divisor (GCD) for more then 2 numbers

If we have more then 2 numbers GCD for them could be found, using the following algorithm:

1. integers: A1, A2, A3
2. GCD1 = GCD(A1, A2)
3. GCD2 = GCD(GCD1, A3)
4. Stop calculation

with 
Input  (Num) as
(select int(56) from sysibm.sysdummy1
 union all
 select     42  from sysibm.sysdummy1
 union all
 select     200977  from sysibm.sysdummy1
 union all
 select     28077771 from sysibm.sysdummy1
 union all
 select     210 from sysibm.sysdummy1
 union all
 select     63 from sysibm.sysdummy1
)
,
GCD_calc(Remd, GCD, lastNo, GCDVW) as
(select Remd, coalesce(GCD, Remd), Remd, 
        Varchar(varchar(varchar(coalesce(GCD, Remd))) || ', ' || varchar(Remd), 5000) 
   from
   (select Remd, GCD
    from 
   (select min(Num) GCD
     from Input      ) m1 
    , table
   (select min(Num) Remd
     from Input  
     where Num > GCD ) m2 ) mm 
Union All
select max(mod(Remd, GCD), GCD), min(mod(Remd, GCD), GCD) , lastNo, GCDVW 
  from GCD_calc 
  where  max(mod(Remd, GCD), GCD) > min(mod(Remd, GCD), GCD) 
    and mod(Remd, GCD) >= 1
Union All
select max(Num, GCD), min(Num, GCD), Num, GCDVW || ', ' || varchar(Num)
     from Input, GCD_calc  
     where Num = (select min(Num) from Input where Num > lastNo) 
       and GCD > 1 
) 
,
GCD(GCD, GCDVW) as
(
select GCD, 'GCD(' || GCDVW || ') = ' || varchar(GCD)  
from 
(select distinct GCD, GCDVW from GCD_calc 
  where remd   = (select min(remd) from GCD_calc)) cc
) 
select GCD "Greatest common divisor", GCDVW "Formula"
  from GCD

Result:

Greatest common divisor............. Formula
.............3................................. GCD(42, 56, 63, 210, 200977, 28077771) = 3

Lenny Khiger, ADSPA&VP