File: coreutils.info,  Node: factor invocation,  Next: numfmt invocation,  Up: Numeric operations

26.1 ‘factor’: Print prime factors
==================================

‘factor’ prints prime factors.  Synopsis:

     factor [OPTION]... [NUMBER]...

   If no NUMBER is specified on the command line, ‘factor’ reads numbers
from standard input, delimited by newlines, tabs, or spaces.

   The program accepts the following options.  Also see *note Common
options::.

‘-h’
‘--exponents’
     print factors in the form p^e, rather than repeating the prime ‘p’,
     ‘e’ times.  If the exponent ‘e’ is 1, then it is omitted.

          $ factor --exponents 3000
          3000: 2^3 3 5^3

   If the number to be factored is small (less than 2^{127} on typical
machines), ‘factor’ uses a faster algorithm.  For example, on a
circa-2017 Intel Xeon Silver 4116, factoring the product of the eighth
and ninth Mersenne primes (approximately 2^{92}) takes about 4 ms of CPU
time:

     $ M8=$(echo 2^31-1 | bc)
     $ M9=$(echo 2^61-1 | bc)
     $ n=$(echo "$M8 * $M9" | bc)
     $ bash -c "time factor $n"
     4951760154835678088235319297: 2147483647 2305843009213693951

     real	0m0.004s
     user	0m0.004s
     sys	0m0.000s

   For larger numbers, ‘factor’ uses a slower algorithm.  On the same
platform, factoring the eighth Fermat number 2^{256} + 1 takes about 14
seconds, and the slower algorithm would have taken about 750 ms to
factor 2^{127} - 3 instead of the 50 ms needed by the faster algorithm.

   Factoring large numbers is, in general, hard.  The Pollard-Brent rho
algorithm used by ‘factor’ is particularly effective for numbers with
relatively small factors.  If you wish to factor large numbers which do
not have small factors (for example, numbers which are the product of
two large primes), other methods are far better.

   An exit status of zero indicates success, and a nonzero value
indicates failure.