Intro To 'factor' Command In Linux
20230619  By Robert Elder
I use the 'factor' command to calculate the prime factors of integers:
factor 14
14: 2 7
Calculating Prime Factors
If I pass a single argument to the 'factor' command, it will print back that same number, followed by a list of prime numbers that would produce the original number when multiplied together:
factor 12345678
12345678: 2 3 3 47 14593
I can also specify more than one number and it will factor all of the numbers at once:
factor 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5
11: 11
12: 2 2 3
13: 13
14: 2 7
15: 3 5
16: 2 2 2 2
17: 17
18: 2 3 3
19: 19
20: 2 2 5
The 'factor' command can even read numbers from standard in. Here is a file called 'numbers.txt':
cat numbers.txt
1
0
2
54
792
3290
88677349
54125119
The list of numbers in this file can be directly piped into the 'factor' command like this:
cat numbers.txt  factor
1:
0:
2: 2
54: 2 3 3 3
792: 2 2 2 3 3 11
3290: 2 5 7 47
88677349: 88677349
54125119: 54125119
You may notice that some of the prime factors (especially 2 and 3) will appear more than once. This is an expected consequence of the Fundamental theorem of arithmetic.
Pollard's Rho Algorithm
In the GNU corelibs implementation of the 'factor' command, you can see it uses 'Pollard's Rho Algorithm to find the prime factors. In the 'factor.c' file, you can see the following piece of code:
...
static void
factor_using_pollard_rho (uintmax_t n, unsigned long int a,
struct factors *factors)
{
uintmax_t x, z, y, P, t, ni, g;
unsigned long int k = 1;
unsigned long int l = 1;
...
Maximum Integer Size & Arbitrary Precision
On my machine the 'factor' command will factor this large number:
# 2^127 1
factor 170141183460469231731687303715884105727
170141183460469231731687303715884105727: 170141183460469231731687303715884105727
but it claims that the number is too large:
# 2^127
factor 170141183460469231731687303715884105728
factor: ‘170141183460469231731687303715884105728’ is too large
The documentation and source code of the 'factor' command implies that it can be compiled in a way that supports arbitrary precision:
info factor
...
If ‘factor’ is built without using GNU MP, only singleprecision
arithmetic is available, and so large numbers (typically 2^{128} and
above) will not be supported. The singleprecision code uses an
algorithm which is designed for factoring smaller numbers.
...
And checking the source of 'factor.c':
17 /* Written by Paul Rubin <phr@ocf.berkeley.edu>.
18 Adapted for GNU, fixed to factor UINT_MAX by Jim Meyering.
19 Arbitraryprecision code adapted by James Youngman from Torbjörn
20 Granlund's factorize.c, from GNU MP version 4.2.2.
21 */
And that's why the 'factor' command is my favourite Linux command.
A Surprisingly Common Mistake Involving Wildcards & The Find Command
Published 20200121 
$1.00 CAD 
A Guide to Recording 660FPS Video On A $6 Raspberry Pi Camera
Published 20190801 
Intro To 'stty' Command In Linux
Published 20231004 
The Most Confusing Grep Mistakes I've Ever Made
Published 20201102 
Intro To 'comm' Command In Linux
Published 20230906 
Use The 'tail' Command To Monitor Everything
Published 20210408 
How To Force The 'true' Command To Return 'false'
Published 20230709 
Join My Mailing List Privacy Policy 
Why Bother Subscribing?
