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 Common options.
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-2021 Intel Xeon W-1350, 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.006s user 0m0.004s sys 0m0.002s
For larger numbers, factor uses a slower algorithm. On the
same platform, factoring the eighth Fermat number 2^{256} + 1
takes about 6400 ms. However, large primes are identified quickly:
it takes just 420 ms to factor the Mersenne prime 2^{11213} - 1
into itself and 1.
Factoring large numbers is, in general, hard. The Pollard–Brent rho
algorithm used by factor is particularly effective for
numbers with relatively small factors. Other methods are far better
for factoring large composite numbers that lack relatively small
factors, such as numbers that are the product of two large primes.
When testing whether a number is prime, factor uses the
Baillie–PSW primality heuristic for speed. Although Baillie–PSW has
not been proven to reject all composite numbers, the probability of a
Baillie–PSW pseudoprime is astronomically small and no such
pseudoprime has been discovered despite decades of searching by
mathematicians. Any such pseudoprime is greater than 2^{64}.
For more, see: Baillie R, Fiori A, Wagstaff Jr SS. Strengthening the
Baillie–PSW primality test. Math Comp. 2021;90:1931–1955.
https://doi.org/10.1090/mcom/3616.
An exit status of zero indicates success, and a nonzero value indicates failure.