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