Just a verbatim mirror of https://rosettacode.org/wiki/Prime_decomposition#jq
"factors" as defined below emits a stream of all the prime factors of the input integer. The implementation is compact, fast and highly space-efficient: no space is required to store the primes or factors already computed, there is no reliance on an "is_prime" function, and square roots are only computed if needed.
The economy comes about through the use of the builtin filter recurse/1, and the use of the state vector: [p, n, valid, sqrt], where p is the candidate factor, n is the number still to be factored, valid is a flag, and sqrt is either null or the square root of n.
The caveat is that the program uses jq's builtin arithmetic operations. Since jq currently uses IEEE 754 64-bit numbers, the following program will only be reliable for integers up to and including 9,007,199,254,740,992 (2^53). However, "factors" could be easily modified to work with a "BigInt" library for jq, such as BigInt.jq.
def factors:
. as $in
| [2, $in, false]
| recurse( .[0] as $p |.[1] as $q | .[2] as $valid | .[3] as $s
| if $q == 1 then empty
elif $q % $p == 0 then [$p, $q/$p, true]
elif $p == 2 then [3, $q, false, $s]
else
($s // ($q | sqrt)) as $s
| if $p + 2 <= $s then [$p + 2, $q, false, $s]
else [$q, 1, true]
end
end )
| if .[2] then .[0] else empty end ;Examples:
[9007199254740992 | factors] | length
#=> 53
# 2**29-1 = 536870911
[ 536870911 | factors ]
#=> [233,1103,2089]
echo \"0124\" | jq '''
def factors:
. as $in
| [2, $in, false]
| recurse( .[0] as $p |.[1] as $q | .[2] as $valid | .[3] as $s
| if $q == 1 then empty
elif $q % $p == 0 then [$p, $q/$p, true]
elif $p == 2 then [3, $q, false, $s]
else
($s // ($q | sqrt)) as $s
| if $p + 2 <= $s then [$p + 2, $q, false, $s]
else [$q, 1, true]
end
end )
| if .[2] then .[0] else empty end ;
tonumber | [factors]
'''