Prime factors of a number

All we know that every natural number (except 1) can be written as a product of prime numbers, and such a decomposition would be unique for each number. This is what the Fundamental theorem of arithmetic is about.

Let's get a query in SQL, which should return (output) a prime factorization of a given natural number (input).

Some time ago I wrote on a OTN forum a query, using model clause, for finding all prime numbers less than a given one. It uses Sieve of Eratosthenes method.

So using this stuff I added one more model part that would iteratively find out all prime factors of a number (one prime factor at an iteration).

And here is my query:

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

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

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
--------------------------------------------------------------------------------
(2^2)
(3^2)
(5^1)
(7^1)
n
---------
1260

SQL>

It was not very effective, e.g. to find prime factors of numbers near 100000 it took about 2 or more minutes to execute on my laptop.

So I decided to post it as challenge on russian SQL.RU forum (russian version and english mirror) and there were pretty good solutions.

But I liked the one from andreymx:

SQL> var p_value number
SQL> exec :p_value:=123432435

PL/SQL procedure successfully completed

Executed in 0,03 seconds
p_value
---------
123432435

SQL>
SQL> set timing on
SQL> WITH s1 AS (SELECT LEVEL lv FROM dual CONNECT BY ROWNUM <= SQRT(:p_value)),
2 s2 AS (SELECT lv id1, :p_value/lv id2 FROM s1 WHERE MOD(:p_value, lv)=0),
3 s3 AS (SELECT id1 ID FROM s2 UNION SELECT id2 FROM s2),
4 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)
5 SELECT :p_value||'='||MAX(LTRIM(RTRIM(SYS_CONNECT_BY_PATH(idd/ID, '*'), '*'), '*')) FROM s4
6 CONNECT BY ID=PRIOR IDd
7 START WITH ID=1
8 /

:P_VALUE||'='||MAX(LTRIM(RTRIM
--------------------------------------------------------------------------------
123432435=3*3*5*7*71*5519

Executed in 0,22 seconds
p_value
---------
123432435

SQL>

As you can see it executes a query for huge numbers less than a second :))
Of course, it depends, but still...

Pair of words about it:
First, he finds all the numbers less than square root of a number (s1).

Then finds all the factors of that number among them and the opposite factor (dividing the number by each factor) (s2).
Thats how he saves a lot of resources.

Then Andrey builds a full list of factors for the initial number (s3).

Then he finds for each factor the next bigger factor which is divided by the current one without rest (s4). This trick was interesting.

At the last step he builds a hierarchy from the 1 factor up to the end (the initial number). All the prime factors are calculated as "child" factor/"parent" factor (IDD/ID in the query).

nice, isn't it? :))