Intro To 'factor' Command In Linux

2023-06-19 - 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

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 single-precision
arithmetic is available, and so large numbers (typically 2^{128} and
above) will not be supported.  The single-precision 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    Arbitrary-precision 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.

Intro To 'stty' Command In Linux Published 2023-10-04	$1.00 CAD Terminal Block Mining Simulation Game	Intro To 'nproc' Command In Linux Published 2023-07-15	Intro To 'comm' Command In Linux Published 2023-09-06
How To Force The 'true' Command To Return 'false' Published 2023-07-09	A Surprisingly Common Mistake Involving Wildcards & The Find Command Published 2020-01-21	A Guide to Recording 660FPS Video On A $6 Raspberry Pi Camera Published 2019-08-01	Intro To 'chroot' Command In Linux Published 2023-06-23

Why Bother Subscribing?

Free Software/Engineering Content. I publish all of my educational content publicly for free so everybody can make use of it. Why bother signing up for a paid 'course', when you can just sign up for this email list?
Read about cool new products that I'm building. How do I make money? Glad you asked! You'll get some emails with examples of things that I sell. You might even get some business ideas of your own :)
People actually like this email list. I know that sounds crazy, because who actually subscribes to email lists these days, right? Well, some do, and if you end up not liking it, I give you permission to unsubscribe and mark it as spam.