Сообщений в теме: 10

[LKhiger]

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(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 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 not in (3, 5, 11)
and
num <= int(sqrt(prime_num + 2)) + 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_num_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 not in (3, 5, 7, 11)
and
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_num_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_num_2
where prime_ind = 'P' 
) 
select prime_num "Prime Number"
from prime_number

You can COPY/PASTE SQL and run.

All prime numbers found in range between 2 and lim.

limit (lim) as 
(select int(1000000) from sysibm.sysdummy1 )

Lenny

[LKhiger]

Разложение целого числа на простые множители.

Проблема не столь проста, как просто решение которое я вам привожу:

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

You may change:

number (number) as 
(select int(2009) from sysibm.sysdummy1)

Lenny

[LKhiger]

Наибольший Общий Делитель (Greatest common divisor):

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 = 56, GCD = 42

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

All next steps using the logics of the Step2

Step3: RemD = 28, GCD = 14

Loop until RemD > 0, or RemD <> GCD

Step4: RemD = 14, GCD = 14

Calculation finished: GCD = 14

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:

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

Lenny

[LKhiger]

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, or not:

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]

Поскольку из чётных чисел простым числом является только 2,
мы можем в два раза ускорить вычисление, убрав из "numbers(num)" все чётные числа, кроме 2:

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]

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

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

[SALar]

Наверное на sql.ru это будет кому то интересно... А сюда то зачем?

[LKhiger]

Наверное на sql.ru это будет кому то интересно... А сюда то зачем?

Я сам менеджер. Правда в США.
Не думаю, что все менеджеры в РФ тыловики. Должны быть и боевые офицеры.

Короче: "Нашальнику тожа шалавек !".

Лёня Хигер.

[LKhiger]

Least common multiple (LCM) -- Наименьшее Общее Кратное (НОК).

In arithmetic and number theory, the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple both of a and of b. Since it is a multiple, it can be divided by a and b without a remainder.
If either a or b is 0, so that there is no such positive integer, then lcm(a, b) is defined to be zero.

The definition is sometimes generalized for more than two integers:
The lowest common multiple of integers a1, ..., an is the smallest positive integer that is a multiple of a1, ..., an.

LCM(a, b) = abs(a * b) / gcd(a, b).

LCM(42, 56) = 42 * 56 / gcd(42, 56) = 42 * 56 / 14 = 42 * 4 = 168.

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  
)
,
GCD(Num1, Num2, GCD) as
(
select Num1, Num2, GCD  
from Input, 
(select GCD from GCD_calc 
  where remd = (select min(remd) from GCD_calc)) cc 
)
,
LCM(Num1, Num2, LCM) as 
(select Num1, Num2, Num1 * Num2 / GCD  
 from GCD )
select Num1, Num2, LCM "Least Common Multiple"
from LCM

Result:

NUM1..... NUM2......Least Common Multiple
42..............56...................168

1/42 + 1/56 = (168/42 + 168/56) / 168 = (4 + 3) / 168 = 7/168

Lenny Khiger, ADSPA&VP

[LKhiger]

Нахождение Наибольшего Общего Делителя для любого количества чисел.

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

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

Actually the order means nothing for the process of calculation GCD, but I have create code using ascending order of the input numbers:

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

[LKhiger]

Галине Т. - девушке из Минска !

Разложение на простые множители очень больших чисел с очень большой скоростью:

with number (number) as 
(select decimal(277945762500, 15, 0) from sysibm.sysdummy1
)
,
fact1(fact) as
(
select decimal(3, 15, 0)   from sysibm.sysdummy1
union all
select fact + 2 
from fact1, number
where fact + 2 <= sqrt(number) + 1
)  
,
factors(fact) as 
(
select 2 from sysibm.sysdummy1
union all
select * from fact1
)  
,
Prime_Factorization (in_number, remd, fact) as
(select number, number, 1 
   from number
union all
select in_number, decimal(pf.remd / coalesce(f1.fact, pf.remd) , 15, 0), 
	  coalesce(f1.fact, pf.remd) 
  from Prime_Factorization pf, 
  table (select min(f2.fact) fact 
		 from factors f2 
		 where mod(pf.remd, f2.fact) = 0  
			and f2.fact <= sqrt(pf.remd) + 1  ) f1
where pf.remd > 1  
) 
select distinct in_number "Number", 
nullif(0, 0) "Prime Factor", nullif(0, 0) "Factor Power"  
from Prime_Factorization 
union all
select nullif(0, 0) "Number", fact "Prime Factor", count(*) "Factor Power" 
from Prime_Factorization 
where fact > 1
group by fact

Number......... Prime Factor......... Factor Power
277945762500
.......................... 2........................... 2
.......................... 3........................... 3
.......................... 5........................... 5
.......................... 7........................... 7

Это результат означает что 277945762500 = 2^2 * 3^3 * 5^5 * 7^7. Можете проверить.

Лёня Х.