jq: prime decomposition ; taken from Rosetta code

Just a verbatim mirror of https://rosettacode.org/wiki/Prime_decomposition#jq

Works with: jq version 1.4

"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]

Usage example


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]
'''