Пятничная задачка: разложение натурального числа в произведение простых / Oracle : Форум на SQL.RU


SQL.RU client/server technologies

Добро пожаловать в форум, Guest >> Войти \| Регистрация \| Поиск \| Правила \|		В избранное \| Подписаться
Все форумы / Oracle

Топик располагается на нескольких страницах: [1] 2 вперед Ctrl→ все

Пятничная задачка: разложение натурального числа в произведение простых [new]
Volder Member Откуда: Москва Сообщений: 471	Известно, что любое натуральное число (не считая 1) представимо в виде произведения простых, причем такое представление будет уникальным. Задача: написать запрос, который будет получать на входе натуральное число, а в результате выдавать произведение простых. Например, подаем на входе 99876, получаем 2^2372941. PS так как натуральные числа не ограничены сверху, и если задать большое число начнуться проблемы с производительностью, для решения данной задачи ограничение сверху - число 100000 есть решение в виде запроса, который при указанных ограничениях, крутится примерно 3 минуты. PPS решения в виде PL/SQL рассматриваются, но только с целью переложения на SQL :))
1 фев 08, 10:37 [5230954] Ответить \| Цитировать Сообщить модератору

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

RA\/EN
Member

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

Volder

Известно, что любое натуральное число (не считая 1) представимо в виде произведения простых, причем такое представление будет уникальным.

Володя, ты мне производственный план срываешь

1 фев 08, 10:55 [5231105] Ответить | Цитировать Сообщить модератору

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

Volder
Member

Откуда: Москва
Сообщений: 471

RA\/EN

Володя, ты мне производственный план срываешь

Кость, ну ты уж расставь приоритеты, что для тебя важнее: какой-то производственный планчик или пятничная задачища

1 фев 08, 11:04 [5231185] Ответить | Цитировать Сообщить модератору

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

RA\/EN
Member

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

Volder

RA\/EN

Володя, ты мне производственный план срываешь

Все, производственный план восстановлен

Ты, наверное, на MODEL решил?

WITH 
 q AS (SELECT 2*2*3*7*11*13*13*17 AS n FROM dual),
q2 AS (SELECT LEVEL p
          FROM q
         CONNECT BY LEVEL <=sqrt(sqrt(n))),
qp AS (
  SELECT *
    FROM (SELECT LEVEL p
            FROM q
           CONNECT BY LEVEL <=sqrt(n)) q1
   WHERE NOT EXISTS (
           SELECT 1
             FROM q2
            WHERE q2.p>1
              AND q2.p<q1.p
              AND MOD(q1.p,q2.p)=0)
     AND q1.p>1),
qd AS (
SELECT DISTINCT 
       dense_rank() over (ORDER BY p) rn,
       p||CASE WHEN COUNT(*) over (PARTITION BY p) >1 THEN '^'||COUNT(*) over (PARTITION BY p) END s,
       SUM(ln(p)) over () alld
  FROM q,qp
 WHERE MOD(n,power(p,LEVEL))=0 
 CONNECT BY NOCYCLE LEVEL<=LOG(p,n)
   AND PRIOR p = p 
   AND dbms_random.value<> PRIOR dbms_random.value)
SELECT MAX(q.n)||' = '||
       max(ltrim(sys_connect_by_path(s,'*'),'*')||
       CASE WHEN round(exp(qd.alld))<>q.n THEN '*'||(q.n/round(exp(qd.alld))) END)
  FROM qd,q
 START WITH rn=1
 CONNECT BY PRIOR rn = rn-1
...

99876 => 2^2*3*7*29*41
2654652 = 2^2*3*7*11*13^2*17
и т.д.

1 фев 08, 11:28 [5231403] Ответить | Цитировать Сообщить модератору

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

RA\/EN
Member

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

RA\/EN

...
99876 => 2^2*3*7*29*41
2654652 = 2^2*3*7*11*13^2*17
и т.д.
[/src]

Это, конечно, будет очень медленно работать для БОООЛЬШИХ чисел, составленных из маленьких множителей. Для такого случая можно поработать с MODEL:

WITH q AS (SELECT 1e38 n FROM dual),
q1 AS (
SELECT *
  FROM q
  MODEL DIMENSION BY(0 i)
  MEASURES (n, 0 AS nn, 2 d)
  RULES ITERATE (1e3) UNTIL (nn[iteration_number]=1) (
    nn[iteration_number] = CASE WHEN iteration_number>0 THEN
                             CASE WHEN mod(nn[iteration_number-1],d[iteration_number-1])=0 THEN
                               nn[iteration_number-1]/d[iteration_number-1]
                             ELSE
                               nn[iteration_number-1]
                             END
                           ELSE
                             n[0]
                           END,
    d[iteration_number]=CASE WHEN iteration_number>0 THEN 
                          CASE WHEN mod(nn[iteration_number-1],d[iteration_number-1])=0 THEN
                            d[iteration_number-1]
                          ELSE 
                            d[iteration_number-1]+1
                          END
                        ELSE
                          2
                        END
                        )),
q2 AS (
SELECT d,CASE WHEN lead(nn,1) over (ORDER BY i) <> nn THEN d END p
  FROM q1)
SELECT q.n||' = '||ltrim(sys_connect_by_path(s,'*'),'*')
  FROM q,
       (SELECT row_number() over (ORDER BY p) rn,
               p||CASE WHEN cnt>1 THEN '^'||cnt END s,
               COUNT(*) over () cnt
          FROM (SELECT p,COUNT(*) cnt
                  FROM q2
                 WHERE p IS NOT NULL
                 GROUP BY p))
 WHERE rn=cnt
 START WITH rn=1 CONNECT BY PRIOR rn = rn-1
                
Результат:
100000000000000000000000000000000000000 = 2^38*5^38
получается за сотые доли секунды

1 фев 08, 11:58 [5231671] Ответить | Цитировать Сообщить модератору

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

Volder
Member

Откуда: Москва
Сообщений: 471

RA\/EN

Ты, наверное, на MODEL решил?

ага, но по производительности намного хуже твоего

RA\/EN

WITH 
 q AS (SELECT 2*2*3*7*11*13*13*17 AS n FROM dual),
q2 AS (SELECT LEVEL p
          FROM q
         CONNECT BY LEVEL <=sqrt(sqrt(n))),
qp AS (
  SELECT *
    FROM (SELECT LEVEL p
            FROM q
           CONNECT BY LEVEL <=sqrt(n)) q1
   WHERE NOT EXISTS (
           SELECT 1
             FROM q2
            WHERE q2.p>1
              AND q2.p<q1.p
              AND MOD(q1.p,q2.p)=0)
     AND q1.p>1),
qd AS (
SELECT DISTINCT 
       dense_rank() over (ORDER BY p) rn,
       p||CASE WHEN COUNT(*) over (PARTITION BY p) >1 THEN '^'||COUNT(*) over (PARTITION BY p) END s,
       SUM(ln(p)) over () alld
  FROM q,qp
 WHERE MOD(n,power(p,LEVEL))=0 
 CONNECT BY NOCYCLE LEVEL<=LOG(p,n)
   AND PRIOR p = p 
   AND dbms_random.value<> PRIOR dbms_random.value)
SELECT MAX(q.n)||' = '||
       max(ltrim(sys_connect_by_path(s,'*'),'*')||
       CASE WHEN round(exp(qd.alld))<>q.n THEN '*'||(q.n/round(exp(qd.alld))) END)
  FROM qd,q
 START WITH rn=1
 CONNECT BY PRIOR rn = rn-1
...

99876 => 2^2*3*7*29*41
2654652 = 2^2*3*7*11*13^2*17
и т.д.

NOCYCLE и DISTINCT так понимаю можно пофигачить.
а вот последняя строка - хитро
сча попробую на свой модел переложить, если получится))

1 фев 08, 12:04 [5231720] Ответить | Цитировать Сообщить модератору

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

Volder
Member

Откуда: Москва
Сообщений: 471

RA\/EN

model ниче так у тебя - идея хорошая

а я строил все простые числа вначале до нужного - это и съедает основное время

PS
кстати, у тебя оба запроса не доведены до ума))
грубо говоря, могу привести число, на котором результат будет некорректный!

1 фев 08, 12:23 [5231878] Ответить | Цитировать Сообщить модератору

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

Volder
Member

Откуда: Москва
Сообщений: 471

Volder

RA\/EN

кстати, у тебя оба запроса не доведены до ума))

про "оба" беру слова обратно, там у модели ты просто итераций мало поставил, а я внимание не обратил.

а вот немоделовский на самом деле кривоват, причем ошибка в корне решения.

1 фев 08, 12:31 [5231963] Ответить | Цитировать Сообщить модератору

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

RA\/EN
Member

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

Volder

PS
так как натуральные числа не ограничены сверху, и если задать большое число начнуться проблемы с производительностью, для решения данной задачи ограничение сверху - число 100000

есть решение в виде запроса, который при указанных ограничениях, крутится примерно 3 минуты.

Слабый у вас там сервачок, первый мой вариант (без MODEL) разложил 1,000,000,000,000 за 200 секунд (в "примерно 3 минуты" уложился

)
Вариант с MODEL, однако, однозначно помрет на большом простом числе. Но его можно доработать по аналогии с первым (это вариант 2.5

WITH q AS (SELECT power(2,31)-1 n FROM dual),
q1 AS (
SELECT *
  FROM q
  MODEL DIMENSION BY(0 i)
  MEASURES (n, 0 AS nn, 2 d)
  RULES ITERATE (1e3) UNTIL (nn[iteration_number]=1 OR d[iteration_number]>sqrt(n[0])) (
    nn[iteration_number] = CASE WHEN iteration_number>0 THEN
                             CASE WHEN mod(nn[iteration_number-1],d[iteration_number-1])=0 THEN
                               nn[iteration_number-1]/d[iteration_number-1]
                             ELSE
                               nn[iteration_number-1]
                             END
                           ELSE
                             n[0]
                           END,
    d[iteration_number]=CASE WHEN iteration_number>0 THEN 
                          CASE WHEN mod(nn[iteration_number-1],d[iteration_number-1])=0 THEN
                            d[iteration_number-1]
                          ELSE 
                            d[iteration_number-1]+1
                          END
                        ELSE
                          2
                        END
                        )),
q2 AS (
SELECT d, CASE WHEN (lead(nn,1) over (ORDER BY i) IS NULL) AND nn<>1 THEN nn 
            ELSE CASE WHEN nvl(lead(nn,1) over (ORDER BY i),nn) <> nn THEN d END END p
  FROM q1)
SELECT q.n||' = '||ltrim(sys_connect_by_path(s,'*'),'*')
  FROM q,
       (SELECT row_number() over (ORDER BY p) rn,
               p||CASE WHEN cnt>1 THEN '^'||cnt END s,
               COUNT(*) over () cnt
          FROM (SELECT p,COUNT(*) cnt
                  FROM q2
                 WHERE p IS NOT NULL
                 GROUP BY p))
 WHERE rn=cnt
 START WITH rn=1 CONNECT BY PRIOR rn = rn-1
--
2147483647 = 2147483647

Заодно нашел глючок в первом варианте: для простых показывает NULL.
Надо доработать его так: (вариант 1.5

WITH 
 q AS (SELECT 2147483647 AS n FROM dual),
q2 AS (SELECT LEVEL p
          FROM q
         CONNECT BY LEVEL <=sqrt(sqrt(n))),
qp AS (
  SELECT *
    FROM (SELECT LEVEL p
            FROM q
           CONNECT BY LEVEL <=sqrt(n)) q1
   WHERE NOT EXISTS (
           SELECT 1
             FROM q2
            WHERE q2.p>1
              AND q2.p<q1.p
              AND MOD(q1.p,q2.p)=0)
     AND q1.p>1)/*
SELECT * FROM qp \**/,
qd AS (
SELECT DISTINCT 
       dense_rank() over (ORDER BY p) rn,
       p||CASE WHEN COUNT(*) over (PARTITION BY p) >1 THEN '^'||COUNT(*) over (PARTITION BY p) END s,
       SUM(ln(p)) over () alld
  FROM q,qp
 WHERE MOD(n,power(p,LEVEL))=0 
 CONNECT BY NOCYCLE LEVEL<=LOG(p,n)
   AND PRIOR p = p 
   AND dbms_random.value<> PRIOR dbms_random.value),
qr AS (
SELECT MAX(q.n)||' = '||
       max(ltrim(sys_connect_by_path(s,'*'),'*')||
       CASE WHEN round(exp(qd.alld))<>q.n THEN '*'||(q.n/round(exp(qd.alld))) END) s,
       COUNT(*) c
  FROM qd,q
 START WITH rn=1
 CONNECT BY PRIOR rn = rn-1)
SELECT CASE WHEN qr.c=0 THEN q.n||' = '||q.n||' (yes, it is prime)'
            ELSE qr.s
       END
  FROM qr,q
--
2147483647 = 2147483647 (yes, it is prime)

1 фев 08, 12:32 [5231972] Ответить | Цитировать Сообщить модератору

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

RA\/EN
Member

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

Volder

RA\/EN

кстати, у тебя оба запроса не доведены до ума))

Уже исправился (версии 1.5 и 2.5)

Ну, скажем, не в "корне", а в самом конце

Или ты имел ввиду другую ошибку?

1 фев 08, 12:35 [5231982] Ответить | Цитировать Сообщить модератору

Re: Пятничная задачка: разложение натурального числа в произведение простых [new]
test_2008 Member Откуда: Москва Сообщений: 1134	with q as ( select t from ( select decode(mod(2000000 , level) , 0 , level , 0) t from dual connect by level<=sqrt(2000000) ) where t>1 ) select replace(wm_concat(mnogitel \|\| '^' \|\| max(stepen)) , ',' , '') from ( select t mnogitel , level stepen 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(2000000* , power(t , level))=0 ) GROUP BY mnogitel Query finished, retrieving results... REPLACE(WM_CONCAT(MNOGITEL\|\|'^ -------------------------------------------------------------------------------- 2^7*5^6
1 фев 08, 12:43 [5232050] Ответить \| Цитировать Сообщить модератору

Re: Пятничная задачка: разложение натурального числа в произведение простых [new]
test_2008 Member Откуда: Москва Сообщений: 1134	Правда моё решение выдаёт все простые до корня .... Скажем для 555 цифру 37 он не выдаст а выдаст тока 3 и 5 ...
1 фев 08, 12:50 [5232107] Ответить \| Цитировать Сообщить модератору

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

Volder
Member

Откуда: Москва
Сообщений: 471

RA\/EN

)

сервачок тут у меня в виде ноутбука, причем потрепанного)))

RA\/EN

Вариант с MODEL, однако, однозначно помрет на большом простом числе. Но его можно доработать по аналогии с первым (это вариант 2.5

точно не помню ограничения на количество итераций, но на 1е10 уже при парсе запроса помирает))

RA\/EN

Заодно нашел глючок в первом варианте: для простых показывает NULL.

ага я про это же, что "в корне ошибка" - попутал

ну раз уж мой вариант все равно переплюнут, вот что было изначально:

SQL> var n number
SQL> exec :n:=99991

PL/SQL procedure successfully completed
n
---------
99991

SQL> set timing on
SQL> 
SQL> with t as (select level l from dual connect by level <= :n),
  2     --
  3      t1 as (select l prim_num from
  4        (select * from t
  5          model
  6           dimension by (l dim)
  7           measures (l,2 temp)
  8            rules iterate (1e8) until (power(temp[1],2)>:n)
  9              (l[DIM>TEMP[1]]=decode(mod(l[CV()],temp[1]),0,null,l[CV()]),
 10               temp[1]=min(l)[dim>temp[1]])
 11        )
 12    where l is not null)
 13    --
 14    select '('||prim_num||'^'||pow||')' prim_factors from (
 15    select * from t1
 16     model
 17      dimension by (rownum rn)
 18      measures(prim_num, :n val, 0 pow)
 19      rules iterate(1000) until (val[1]=1)
 20      (pow[any] order by rn = decode(mod(val[1],prim_num[CV()]),0,pow[CV()]+1,pow[CV()]),
 21       val[rn>1] order by rn = decode(mod(val[CV()-1],prim_num[CV()]),0,val[CV()-1]/prim_num[CV()],val[CV()-1]),
 22       val[1]=min(val)[any]))
 23       where rn>1 and pow>0
 24  /

PRIM_FACTORS
--------------------------------------------------------------------------------
(99991^1)

Executed in 146.25 seconds
n
---------
99991

SQL> exec :n:=999

PL/SQL procedure successfully completed

Executed in 0 seconds
n
---------
999

SQL> 
SQL> with t as (select level l from dual connect by level <= :n),
  2     --
  3      t1 as (select l prim_num from
  4        (select * from t
  5          model
  6           dimension by (l dim)
  7           measures (l,2 temp)
  8            rules iterate (1e8) until (power(temp[1],2)>:n)
  9              (l[DIM>TEMP[1]]=decode(mod(l[CV()],temp[1]),0,null,l[CV()]),
 10               temp[1]=min(l)[dim>temp[1]])
 11        )
 12    where l is not null)
 13    --
 14    select '('||prim_num||'^'||pow||')' prim_factors from (
 15    select * from t1
 16     model
 17      dimension by (rownum rn)
 18      measures(prim_num, :n val, 0 pow)
 19      rules iterate(1000) until (val[1]=1)
 20      (pow[any] order by rn = decode(mod(val[1],prim_num[CV()]),0,pow[CV()]+1,pow[CV()]),
 21       val[rn>1] order by rn = decode(mod(val[CV()-1],prim_num[CV()]),0,val[CV()-1]/prim_num[CV()],val[CV()-1]),
 22       val[1]=min(val)[any]))
 23       where rn>1 and pow>0
 24  /

PRIM_FACTORS
--------------------------------------------------------------------------------
(3^3)
(37^1)

Executed in 0.25 seconds
n
---------
999

SQL>

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

1 фев 08, 13:05 [5232234] Ответить | Цитировать Сообщить модератору

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

test_2008
Member

Откуда: Москва
Сообщений: 1134

автор

Слабый у вас там сервачок, первый мой вариант (без MODEL) разложил 1,000,000,000,000 за 200 секунд (в "примерно 3 минуты" уложился )

Мой вариант Statement processed in 3,31 sec для 1000000000000.

1 фев 08, 13:07 [5232247] Ответить | Цитировать Сообщить модератору

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

Volder
Member

Откуда: Москва
Сообщений: 471

test_2008

Правда моё решение выдаёт все простые до корня ....
Скажем для 555 цифру 37 он не выдаст а выдаст тока 3 и 5 ...

очень плохо, что не выдает))

1 фев 08, 13:09 [5232262] Ответить | Цитировать Сообщить модератору

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

test_2008
Member

Откуда: Москва
Сообщений: 1134

Volder

test_2008

Правда моё решение выдаёт все простые до корня ....
Скажем для 555 цифру 37 он не выдаст а выдаст тока 3 и 5 ...

очень плохо, что не выдает))

Парсек почти дописал с тем чтобы выдавал ...

1 фев 08, 13:11 [5232271] Ответить | Цитировать Сообщить модератору

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

RA\/EN
Member

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

test_2008

Правда моё решение выдаёт все простые до корня ....
Скажем для 555 цифру 37 он не выдаст а выдаст тока 3 и 5 ...

Клевая идея - не искать все простые делители, а найти все любые делители и потом найти уже по их набору простые - работает в N^0.25 быстрее, чем первоначальный подбор всех простых (как я его искал)
Приблизительно это используется в версии с MODEL (2.5). На обычный SQL переложить не додумался...

1 фев 08, 13:23 [5232367] Ответить | Цитировать Сообщить модератору

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

Volder
Member

Откуда: Москва
Сообщений: 471

test_2008

Парсек почти дописал с тем чтобы выдавал ...

ужo написали:

RAVEN

...SELECT MAX(q.n)||' = '||
       max(ltrim(sys_connect_by_path(s,'*'),'*')||
       CASE WHEN round(exp(qd.alld))<>q.n THEN '*'||(q.n/round(exp(qd.alld))) END) s,
       COUNT(*) c
  FROM qd,q
 START WITH rn=1
 CONNECT BY PRIOR rn = rn-1)
SELECT CASE WHEN qr.c=0 THEN q.n||' = '||q.n||' (yes, it is prime)'
            ELSE qr.s
       END
  FROM qr,q

1 фев 08, 13:23 [5232369] Ответить | Цитировать Сообщить модератору

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

test_2008
Member

Откуда: Москва
Сообщений: 1134

with 
q as 
            (
        select t  from (
            select decode(mod(555 , level) , 0 , level , 0) t from dual connect by level<=sqrt(555)
        ) 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(555 , power(t , level))=0
)
GROUP BY mnogitel
            ) , 
last_primary as (
    select 555/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

тока наскока можно доверять точности trunc(exp(sum(ln(power(mnogitel , stepen))))) неизвестно ...
Блин почему нету агрегационного произведения

1 фев 08, 13:38 [5232508] Ответить | Цитировать Сообщить модератору

Re: Пятничная задачка: разложение натурального числа в произведение простых [new]
test_2008 Member Откуда: Москва Сообщений: 1134	Кто рискнёт вероятностный ро-Метод Полларда факторизации на SQL переложить ? Работает тоже довольно быстро ....
1 фев 08, 13:52 [5232610] Ответить \| Цитировать Сообщить модератору

Re: Пятничная задачка: разложение натурального числа в произведение простых [new]
test_2008 Member Откуда: Москва Сообщений: 1134	Кстати можно перефразировать задачу ..... Есть число с количество цифр в десятичной записи > 10.000 ..... Найти множество цифр его первого простого делителя ....
1 фев 08, 14:10 [5232726] Ответить \| Цитировать Сообщить модератору

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

RA\/EN
Member

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

test_2008

Кто рискнёт вероятностный ро-Метод Полларда факторизации на SQL переложить ?
Работает тоже довольно быстро ....
...
Кстати можно перефразировать задачу .....
Есть число с количество цифр в десятичной записи > 10.000 .....
Найти множество цифр его первого простого делителя ....

Я думаю, извращенца не найдется.
Решать на SQL сложные алгоритмически задачи не интересно, т.к. получается не SQL, а хрен пойми что.
Давай ты напишешь на PURE SQL реализацию RSA-подписи CLOB-а по 2048-битному ключу, и тогда будешь предлагать задачки, аналогичные или идентичные отцитированным?

1 фев 08, 15:37 [5233578] Ответить | Цитировать Сообщить модератору

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

test_2008
Member

Откуда: Москва
Сообщений: 1134

RA\/EN

test_2008

Да не надо так всё болезненно воспринимать ....
Это так больше шутка даже...
Я просто занимался этим и реализовывал вышеуказанное на языке Си .....
А это так в довесок к пятничному ребусу

1 фев 08, 15:39 [5233603] Ответить | Цитировать Сообщить модератору

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

test_2008
Member

Откуда: Москва
Сообщений: 1134

автор

Давай ты напишешь на PURE SQL реализацию RSA-подписи CLOB-а по 2048-битному ключу, и тогда будешь предлагать задачки, аналогичные или идентичные отцитированным?

Жесть какая господи ...

1 фев 08, 15:40 [5233615] Ответить | Цитировать Сообщить модератору

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

RA\/EN
Member

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

test_2008

...
тока наскока можно доверять точности trunc(exp(sum(ln(power(mnogitel , stepen))))) неизвестно ...
Блин почему нету агрегационного произведения

Ошибка начнется для чисел, больших, чем:

SQL> SELECT power(MIN(power(2,n)),2)
  2    FROM (SELECT LEVEL n,
  3                 power(2,LEVEL)-round(exp(ln(2)*LEVEL)) delta
  4            FROM dual CONNECT BY LEVEL <=128)
  5   WHERE delta<>0
  6  /
 
POWER(MIN(POWER(2,N)),2)
------------------------
     1,76684706477838E72
 
SQL>

NUMBER в оракле при этом уже все равно потеряет младшие разряды, так что и говорить о разложении бессмыссленно.

Говорить о решении все равно бессмысленно, т.к. даже у решения с MODEL, которое, хоть и раскладывает 10e38 за долю секнуды, все равно имеет верний предел SQRT(N), а для 1E72 это будет 1E36, что приблизительно рассчитается за срок, в 422,797,226,450 раз превышающий возраст вселенной. Не говоря уж о том, что Oracle не позволит произвести такой расчет из-за ограничений на размер SGA и файлов базы данных.

1 фев 08, 15:54 [5233753] Ответить | Цитировать Сообщить модератору

Топик располагается на нескольких страницах: [1] 2 вперед Ctrl→ все

Все форумы / Oracle

Generated time: 250ms.