SQL.RU
 client/server technologies
 
 Главная | Документация | Статьи | Книги | Форум | Опросы | Рассылка | Работа | Поиск | FAQ |

Добро пожаловать в форум, Guest  >>  Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик  Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
RA\/EN
Member

Откуда:
Сообщений: 3244
Volder

PS сколько по времени на вашем сервачке первый запрос открутится?

113 секунд.
Ну вообще на MODEL сам бог велел делать задачу рекурсивно
Ты вообще аццки model пользуешь, я заметил :) На отчетах центральной банки натренировался?
1 фев 08, 16:31    [5234091] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
Volder
Member

Откуда: Москва
Сообщений: 471
RA\/EN
На отчетах центральной банки натренировался?
фтопку их :)) вспоминаю аки страшный сон

про пятничную задачку - всем спасибо за участие.
итеративно на самом деле значительно лучшее.

но вот, кстати, ее если немного перевернуть и сформулировать, например, как
"получить с помощью запроса наименьшее простое число, которое превышает, скажем, 500000", то эдак можно и на следующую пятничку перенести))
1 фев 08, 17:12    [5234399] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 8262
Volder
сформулировать, например, как "получить с помощью запроса наименьшее простое число, которое превышает, скажем, 500000", то эдак можно и на следующую пятничку перенести))
WITH s1 AS (SELECT	LEVEL*6+:p_value-MOD(:p_value, 6) ID FROM	dual CONNECT BY ROWNUM<=201),
	 s2 AS (SELECT -1 d FROM dual UNION ALL SELECT 1 FROM dual),
	 s3 AS (SELECT	ROWNUM*6 ID FROM	dual CONNECT BY LEVEL*6 < SQRT(:p_value)+10000),
	 s4 AS (SELECT	ID+d ID FROM	s3, s2),
	 forsimple AS (SELECT	ID+d forsimple  FROM s1,s2)
SELECT	forsimple min_simple
FROM	forsimple f1
WHERE	NOT EXISTS(SELECT NULL FROM s4 WHERE MOD(f1.forsimple, s4.ID)=0)
AND ROWNUM=1
500000 => 500009
5000000 => 5000011
50000000 => 50000017
500000000000 => 500000000023
5000000000000 => 5000000000053
2 фев 08, 01:26    [5235880] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
Volder
Member

Откуда: Москва
Сообщений: 471
andreymx
..
Андрей, а можешь поподробней алгоритм объяснить и больше про ограничения запроса, в связи со всякими вставками констант вроде "6", "10000", "201".

например, на 500012 неправильно работает:
SQL> WITH t as (select 500112 p_value from dual),
  2     s1 AS (SELECT	LEVEL*6+p_value-MOD(p_value, 6) ID FROM	t CONNECT BY ROWNUM<=201),
  3  	 s2 AS (SELECT -1 d FROM dual UNION ALL SELECT 1 FROM dual),
  4  	 s3 AS (SELECT	ROWNUM*6 ID FROM	t CONNECT BY LEVEL*6 < SQRT(p_value)+10000),
  5  	 s4 AS (SELECT	ID+d ID FROM	s3, s2),
  6  	 forsimple AS (SELECT	ID+d forsimple  FROM s1,s2)
  7  SELECT	forsimple min_simple
  8  FROM	forsimple f1
  9  WHERE	NOT EXISTS(SELECT NULL FROM s4 WHERE MOD(f1.forsimple, s4.ID)=0)
 10  AND ROWNUM=1
 11  /

MIN_SIMPLE
----------
    500119

SQL> 
а должон 500113 возвращать
2 фев 08, 14:54    [5236338] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 8262
ошибка была в определении минимального числа s1.id ))))
WITH s1 AS (SELECT	LEVEL*6+:p_value-MOD(:p_value, 6)-6 ID FROM	dual CONNECT BY ROWNUM<=201),
	 s2 AS (SELECT -1 d FROM dual UNION ALL SELECT 1 FROM dual),
	 s3 AS (SELECT	ROWNUM*6 ID FROM	dual CONNECT BY LEVEL*6 < SQRT(:p_value)+10000),
	 s4 AS (SELECT	ID+d ID FROM	s3, s2),
	 forsimple AS (SELECT	ID+d forsimple  FROM s1,s2 WHERE ID+d>=:p_value)
SELECT	forsimple min_simple
FROM	forsimple f1
WHERE	NOT EXISTS(SELECT NULL FROM s4 WHERE MOD(f1.forsimple, s4.ID)=0)
AND ROWNUM=1
Все простые числа, которые больше 3, находятся в диапазоне 6N +/-1.
201 - это беру 402 числа (запрос forsimple) из этого диапазона, которые >= :p_value (это от фонаря). От того же фонаря и 100000.
2 фев 08, 18:14    [5236586] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
Volder
Member

Откуда: Москва
Сообщений: 471
andreymx
Все простые числа, которые больше 3, находятся в диапазоне 6N +/-1.
не знал, ну чтож здорово)))
2 фев 08, 23:52    [5237129] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 8262
А такого варианта разложения вроде еще не было?
WITH -- все числа меньше SQRT(:p_value)
	 s1 AS (SELECT ROWNUM+1 ID FROM dual CONNECT BY ROWNUM < SQRT(:p_value)),
	 -- делители парами
	 s2 AS (SELECT	ID, :p_value / ID id1 FROM s1 WHERE	MOD(:p_value, ID)=0),
	 -- делители в одну колонку
	 s3 AS (SELECT	CASE WHEN lv =1 THEN ID ELSE id1 END  ID FROM s2, (SELECT LEVEL lv FROM dual CONNECT BY LEVEL < 3) ORDER BY ID),
	 -- разделим делители на другие делители из нашего запроса 
	 s4 AS (SELECT	ID id_parent, 
		(SELECT MAX(s3_2.ID) FROM s3 s3_2 WHERE ABS(TRUNC(s3_1.ID/s3_2.ID)-s3_1.ID/s3_2.ID)< .00000000000001 AND s3_1.ID>s3_2.ID) ID 
		FROM s3 s3_1),
	 -- проход по дереву; ищем id2 - собссно простые делители
	 s5 AS (SELECT LTRIM(SYS_CONNECT_BY_PATH(ID, '*')||'*'||ID_parent, '*')||'*' id1,
				  LTRIM(SYS_CONNECT_BY_PATH(ID_parent/ID, '*'), '*') id2
			FROM s4 CONNECT BY PRIOR id_parent=ID),
	s6 AS (SELECT DISTINCT  SUBSTR(id1, 1, INSTR(id1, '*'))||id2 ID FROM s5)
	SELECT	MAX(ID) ID
	FROM s6
	WHERE (SUBSTR(ID, LENGTH(ID), 1) = '*' OR ID LIKE '%*'||SUBSTR(ID, 1, INSTR(ID, '*')-1))
	GROUP BY SUBSTR(ID, 1, INSTR(ID, '*'))
	UNION SELECT :p_value||'*' FROM dual WHERE NOT EXISTS(SELECT NULL FROM s6)
	ORDER BY ID
Только уж не подрабатывал напильником - чтобы красиво в строку
:p_value = 1000000000000, 3 сек
Row#ID
12*2*2*2*2*2*2*2*2*2*2*2
25*5*5*5*5*5*5*5*5*5*5*5
:p_value = 1000000000001, 4 сек
Row#ID
1137*
273*
399990001*
:p_value = 100000000001, 1 сек
Row#ID
111*11
223*
34093*
48779*
2 фев 08, 23:59    [5237140] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 8262
глюк нашёл - неверное разлагает числа, являющиеся степенью одного простого числа - типа 27, 64, 625 (((((
3 фев 08, 00:34    [5237165] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 8262
WITH s1 AS (SELECT	LEVEL lv FROM	dual CONNECT BY ROWNUM <= SQRT(:p_value)),
	 s2 AS (SELECT	lv id1, :p_value/lv id2 FROM s1 WHERE MOD(:p_value, lv)=0),
	 s3 AS (SELECT	CASE WHEN lv=1 THEN id1 ELSE id2 END ID FROM s2, s1 WHERE lv < 3 UNION SELECT TO_NUMBER(:p_value) FROM dual ORDER BY ID),
	 s4 AS (SELECT	row_number() OVER(ORDER BY ID) rn, ID, lead(ID, 1) OVER(ORDER BY ID), lead(ID, 1) OVER(ORDER BY ID) / ID  id3 FROM s3),
	 s5 AS (SELECT	ID, (SELECT MIN(ID) FROM s4 s4_1 WHERE s4_1.ID / s4.ID = TRUNC(s4_1.ID / s4.ID) AND s4_1.ID > s4.ID) idd FROM s4)
SELECT MAX(LTRIM(RTRIM(SYS_CONNECT_BY_PATH(idd/ID, '*'), '*'), '*')) FROM s5
CONNECT BY ID=PRIOR IDd
START WITH ID=1
Только на домашней тачке пошустрее в десятки раз
3 фев 08, 10:09    [5237297] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 8262
WITH s1 AS (SELECT LEVEL lv FROM dual CONNECT BY ROWNUM <= SQRT(:p_value)), 
     s2 AS (SELECT lv id1, :p_value/lv id2 FROM s1 WHERE MOD(:p_value, lv)=0), 
     s3 AS (SELECT id1 ID FROM s2 UNION SELECT id2 FROM s2), 
     s4 AS (SELECT ID, (SELECT MIN(ID) FROM s3 s3_1 WHERE s3_1.ID / s3.ID = TRUNC(s3_1.ID / s3.ID) AND s3_1.ID > s3.ID) idd FROM s3) 
SELECT :p_value||'='||MAX(LTRIM(RTRIM(SYS_CONNECT_BY_PATH(idd/ID, '*'), '*'), '*')) FROM s4
CONNECT BY ID=PRIOR IDd
START WITH ID=1
Ето всё ))))
3 фев 08, 13:53    [5237579] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
Volder
Member

Откуда: Москва
Сообщений: 471
test_2008
тока наскока можно доверять точности trunc(exp(sum(ln(power(mnogitel , stepen))))) неизвестно ...
а какая логика была для trunc, а не round?
SQL> with
  2  q as
  3              (
  4          select t  from (
  5              select decode(mod(500 , level) , 0 , level , 0) t from dual connect by level<=sqrt(500)
  6          ) where t>1
  7              ) ,
  8  result as   (
  9  select mnogitel ,   max(st) stepen from (
 10  select t mnogitel , level st from (
 11  select q1.t from q q1 left join q q2 ON mod(q1.t , q2.t)=0 and q1.t != q2.t
 12  WHERE q2.t is null
 13  ) connect by t=prior t and prior dbms_random.value is not null and mod(500 , power(t , level))=0
 14  )
 15  GROUP BY mnogitel
 16              ) ,
 17  last_primary as (
 18      select 500/trunc(exp(sum(ln(power(mnogitel , stepen))))) , 1 from result
 19                  )
 20  select replace(wm_concat(mnogitel || '^' ||  stepen) , ',' , '*') from
 21  (
 22  select * from result
 23  union
 24  select * from last_primary
 25  ) where mnogitel>1
 26  /

REPLACE(WM_CONCAT(MNOGITEL||'^
--------------------------------------------------------------------------------
1*00200400801603206412825651302605210421^1*2^2*5^3

SQL> 
+ простые числа не раскладываются
with 
q as 
            (
        select t  from (
            select decode(mod(5 , level) , 0 , level , 0) t from dual connect by level<=sqrt(5)
        ) where t>1 
            ) ,
result as   (
select mnogitel ,   max(st) stepen from (
select t mnogitel , level st from (
select q1.t from q q1 left join q q2 ON mod(q1.t , q2.t)=0 and q1.t != q2.t
WHERE q2.t is null
) connect by t=prior t and prior dbms_random.value is not null and mod(5 , power(t , level))=0
)
GROUP BY mnogitel
            ) , 
last_primary as (
    select 5/trunc(exp(sum(ln(power(mnogitel , stepen))))) , 1 from result 
                )
select replace(wm_concat(mnogitel || '^' ||  stepen) , ',' , '*') from
(
select * from result
union 
select * from last_primary 
) where mnogitel>1

andreymx
Ето всё ))))

здорово, иерархия по делителям понравилась
3 фев 08, 19:33    [5238064] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
test_2008
Member

Откуда: Москва
Сообщений: 1127
with
   q as
               (
           select t  from (
               select decode(mod(37 , level) , 0 , level , 0) t from dual connect by level<=sqrt(37)
           ) where t>1
               ) ,
   result as   (
   select mnogitel ,   max(st) stepen from (
   select t mnogitel , level st from (
   select q1.t from q q1 left join q q2 ON mod(q1.t , q2.t)=0 and q1.t != q2.t
   WHERE q2.t is null
   ) connect by t=prior t and prior dbms_random.value is not null and mod(37 , power(t , level))=0
   )
   GROUP BY mnogitel
               ) ,
   last_primary as (
       select nvl(37/round(exp(sum(ln(power(mnogitel , stepen))))) , 37) , 1 from result
                   )
   select replace(wm_concat(mnogitel || '^' ||  stepen) , ',' , '*') from
   (
   select * from result
   union
   select * from last_primary
   ) where mnogitel>1
Так работает и для простых
плюс trunc на round заменил
3 фев 08, 20:49    [5238199] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 8335
andreymx
..Ето всё ))))

мне (тоже) понравилось :)

Сомнение вызвал (исходный) шаг s4. Попробовал подкрутить - что вышло см. ниже

set echo off
spool o1

var v1 number
var v2 number
var v3 number

exec :v1 := 1000000000000;
exec :v2 := power(2,40);
exec :v3 := 1307674368000;

var v number
exec :v := :v1;
set timing on
with s1 as (select level lv from dual connect by rownum <= sqrt(:v))
    ,s2 as (select lv id1, :v/lv id2 from s1 where mod(:v, lv)=0 and lv>1)
    ,s3 as (select id1 id from s2 union select id2 from s2)
    ,s4 as (select b.id
              from s3 b
             where not exists(select id from s3 a
                              where a.id <= sqrt(b.id)
                                and mod(b.id,a.id) = 0) )
    ,s5 as (select decode(max(level),1,to_char(id),id||'^'||max(level)) a
              from s4
        connect by mod(:v, power(id,level)) = 0
          group by id
          order by id )
    ,s6 as (select a ,rownum r from s5
      union select to_char(:v), 1 from dual where (select count(*) from s5)=0)
 select :v||'='||replace(substr(max(sys_connect_by_path(a,'*')),2),'*',' * ') r
   from s6 start with r = 1 connect by r = prior r+1
;
exec :v := :v2;
/
exec :v := :v3;
/

var p_value number
exec :p_value := :v1;
WITH s1 AS (SELECT LEVEL lv FROM dual CONNECT BY ROWNUM <= SQRT(:p_value)),
     s2 AS (SELECT lv id1, :p_value/lv id2 FROM s1 WHERE MOD(:p_value, lv)=0),
     s3 AS (SELECT id1 ID FROM s2 UNION SELECT id2 FROM s2),
     s4 AS (SELECT ID, (SELECT MIN(ID) FROM s3 s3_1
     WHERE s3_1.ID / s3.ID = TRUNC(s3_1.ID / s3.ID) AND s3_1.ID > s3.ID) idd FROM s3)
SELECT :p_value||'='||MAX(LTRIM(RTRIM(SYS_CONNECT_BY_PATH(idd/ID, '*'), '*'), '*'))
as res FROM s4
CONNECT BY ID=PRIOR IDd
START WITH ID=1
;
exec :p_value := :v2;
/
exec :p_value := :v3;
/

оутпут
R
--------------------------------------------------------------------------------
1000000000000=2^12 * 5^12
Затрач.время: 00:00:03.76

1099511627776=2^40
Затрач.время: 00:00:04.01

1307674368000=2^11 * 3^6 * 5^3 * 7^2 * 11 * 13
Затрач.время: 00:00:05.64


RES
--------------------------------------------------------------------------------
1000000000000=2*2*2*2*2*2*2*2*2*2*2*2*5*5*5*5*5*5*5*5*5*5*5*5
Затрач.время: 00:00:03.55

1099511627776=2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*
2*2*2*2*2*2*2
Затрач.время: 00:00:03.84

1307674368000=2*2*2*2*2*2*2*2*2*2*2*3*3*3*3*3*3*5*5*5*7*7*11*13
Затрач.время: 00:00:22.50
Ну, т.е. ничего особенного (у меня) не вышло - всё даже хуже,
кроме v3 - (это факториал пятнадцати)
4 фев 08, 20:10    [5242962] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 8262
orawish
1307674368000=2*2*2*2*2*2*2*2*2*2*2*3*3*3*3*3*3*5*5*5*7*7*11*13
Затрач.время: 00:00:22.50
Я теперь спать и жрать перестал )))))
5 фев 08, 13:53    [5246192] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
test_2008
Member

Откуда: Москва
Сообщений: 1127
WITH s1 AS (SELECT LEVEL lv FROM dual CONNECT BY ROWNUM <= SQRT('1307674368000')), 
     s2 AS (SELECT lv id1, '1307674368000'/lv id2 FROM s1 WHERE MOD('1307674368000', lv)=0), 
     s3 AS (SELECT id1 ID FROM s2 UNION SELECT id2 FROM s2), 
     s4 AS (SELECT ID, (SELECT MIN(ID) FROM s3 s3_1 WHERE s3_1.ID / s3.ID = TRUNC(s3_1.ID / s3.ID) AND s3_1.ID > s3.ID) idd FROM s3) 
SELECT '1307674368000'||'='||MAX(LTRIM(RTRIM(SYS_CONNECT_BY_PATH(idd/ID, '*'), '*'), '*')) FROM s4
CONNECT BY ID=PRIOR IDd
START WITH ID=1
Query finished, retrieving results...
'1307674368000'||'='||MAX(LTRI
--------------------------------------------------------------------------------
1307674368000=2*2*2*2*2*2*2*2*2*2*2*3*3*3*3*3*3*5*5*5*7*7*11*13
Statement processed in 14,75 sec;


with
   q as
               (
           select t  from (
               select decode(mod(1307674368000 , level) , 0 , level , 0) t from dual connect by level<=sqrt(1307674368000)
           ) where t>1
               ) ,
   result as   (
   select mnogitel ,   max(st) stepen from (
   select t mnogitel , level st from (
   select q1.t from q q1 left join q q2 ON mod(q1.t , q2.t)=0 and q1.t != q2.t
   WHERE q2.t is null
   ) connect by t=prior t and prior dbms_random.value is not null and mod(1307674368000 , power(t , level))=0
   )
   GROUP BY mnogitel
               ) ,
   last_primary as (
       select nvl(1307674368000/round(exp(sum(ln(power(mnogitel , stepen))))) , 1307674368000) , 1 from result
                   )
   select replace(wm_concat(mnogitel || '^' ||  stepen) , ',' , '*') from
   (
   select * from result
   union
   select * from last_primary
   ) where mnogitel>1

Query finished, retrieving results...
REPLACE(WM_CONCAT(MNOGITEL||'^
--------------------------------------------------------------------------------
2^11*3^6*5^3*7^2*11^1*13^1
Statement processed in 7,73 sec;



Почти в два раза ...
5 фев 08, 16:27    [5247414] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 8262
Как злобные мухи на мой красивенький запросик налетели )))))))))))))
5 фев 08, 17:41    [5248065] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
test_2008
Member

Откуда: Москва
Сообщений: 1127
with
     s1 as   (select level  t from dual WHERE mod(1307674368000 , level)=0 and level>1 connect by level<=sqrt(1307674368000)) ,
     s2 as   (select q1.t from s1 q1 left join s1 q2 ON mod(q1.t , q2.t)=0 and q1.t != q2.t WHERE q2.t is null)  ,
     s3 as   (select t mnogitel , max(level) stepen from s2 connect by t=prior t and prior dbms_random.value is not null and 
     mod(1307674368000 , power(t , level))=0  GROUP BY t) ,
     s4 as   (select nvl(1307674368000/round(exp(sum(ln(power(mnogitel , stepen))))) , 1307674368000) , 1 from s3)
select replace(wm_concat(mnogitel || '^' ||  stepen) , ',' , '*') from (select * from s3 union select * from s4) 
where mnogitel>1

Теперь и мой красивенький
5 фев 08, 18:13    [5248300] Ответить | Цитировать    Сообщить модератору

 Re: Пятничная задачка: разложение натурального числа в произведение простых   [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 8262
Маленький финт ушами, и время упало в 2 раза:
WITH s1 AS (SELECT LEVEL lv FROM dual CONNECT BY ROWNUM <= SQRT(:p_value)), 
     s2 AS (SELECT lv id1, :p_value/lv id2 FROM s1 WHERE MOD(:p_value, lv)=0), 
     s3 AS (SELECT id1 ID FROM s2 UNION SELECT id2 FROM s2), 
     s4 AS (SELECT ID, (SELECT MIN(ID) FROM s3 s3_1 WHERE s3_1.ID / s3.ID = TRUNC(s3_1.ID / s3.ID) AND s3_1.ID > s3.ID 
AND ROWNUM=1
) idd FROM s3) 
SELECT :p_value||'='||MAX(LTRIM(RTRIM(SYS_CONNECT_BY_PATH(idd/ID, '*'), '*'), '*')) FROM s4
CONNECT BY ID=PRIOR IDd
START WITH ID=1
5 фев 08, 23:29    [5248994] Ответить | Цитировать    Сообщить модератору

Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
Все форумы / Oracle Ответить
Generated time: 359ms.
Rambler's Top100 Powered by ActualForum 1.5.3 [s1] Copyright (c) Alex Sibilev 2000-2010