VPF::Нахождение простых чисел - Форум программистов

LKhiger

Дата 11.9.2009, 06:37 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 7.9.2009

Репутация: 2
Всего: 2

Простые числа - это числа, имеющие делителями только 1 и себя.

Вот ряд: 2, 3, 5, 7, 11, .... и т.д.

Не существует формулы для нахождения простых чисел. Увы !

1 не является простым числом.

Я не использовал решета Эрастофена.

Что нового ?

Для ускорения я создал каскад: Сначала нахожу все простые числа на отрезке Х от 2 до SQRT(lim)

Затем, используя этот результат нахожу все простые числа отрезке Х от SQRT(lim) до lim.

Для ускорения я также использовал признаки деления на простые числа: 3, 5, 7, 11....

Код


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

Lenny Khiger

Это сообщение отредактировал(а) LKhiger - 11.9.2009, 06:38

LKhiger

Дата 13.9.2009, 04:23 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 7.9.2009

Репутация: 2
Всего: 2

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

Мы не будем использовать результат нахождения простых чисел из прошлого примера. smile

Код


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 Khiger

LKhiger

Дата 20.9.2009, 02:13 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 7.9.2009

Репутация: 2
Всего: 2

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.

Код


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 + 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 - 20.9.2009, 06:39

LKhiger

Дата 20.9.2009, 06:08 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 7.9.2009

Репутация: 2
Всего: 2

Поскольку из чётных чисел простым числом является только 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 - 20.9.2009, 06:10

LKhiger

Дата 20.9.2009, 16:46 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 7.9.2009

Репутация: 2
Всего: 2

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

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Другие СУБД \| Следующая тема »