30 lines
853 B
Plaintext
30 lines
853 B
Plaintext
create or replace function prime_factors(nn) as table (
|
|
with recursive cte(p, q, valid, s) as (
|
|
select 2::UHUGEINT as p, nn::UHUGEINT as q, false as valid, null::DOUBLE as s
|
|
union all
|
|
select unnest(
|
|
if (q = 1, (0, 0, false, null),
|
|
if (q % p = 0, (p, q // p, true, null),
|
|
if (p = 2, (3, q, false, s),
|
|
if (p + 2 <= coalesce(s, sqrt(q)),
|
|
(p + 2, q, false, coalesce(s, sqrt(q))),
|
|
(q, 1, true, null) )))) )
|
|
from cte
|
|
where p != 0
|
|
)
|
|
select p
|
|
from cte
|
|
where valid
|
|
);
|
|
|
|
## Examples
|
|
|
|
.print The prime factors of 24:
|
|
from prime_factors(24);
|
|
|
|
.print The prime factors of 2**29-1 = 536870911
|
|
from prime_factors(536870911);
|
|
|
|
.print Counting the prime factors of 9007199254740992:
|
|
select count(*) from prime_factors(9007199254740992);
|