Factor

From LQWiki
Jump to: navigation, search

The factor command shows the prime factors of a positive integer. The program can handle numbers up to 18446744073709551615 (2^64 - 1) on a 32-bit machine, or 170141183460469231731687303715884105727 (2^127-1) on a 64-bit machine.


Examples

On a 32-bit machine

$ factor 1920 1080
1920: 2 2 2 2 2 2 2 3 5
1080: 2 2 2 3 3 3 5

$ factor 18446744073709551616
factor: `18446744073709551616' is too large
$ factor 18446744073709551615        (the largest number it can process on a 32-bit machine)
18446744073709551615: 3 5 17 257 641 65537 6700417
$ factor 18446744073709551557
18446744073709551557: 18446744073709551557    (the largest prime it can verify on a 32-bit machine)

On a 64-bit machine

$ factor 170141183460469231731687303715884105727
170141183460469231731687303715884105727: 170141183460469231731687303715884105727 (the largest number it can process on a 64-bit machine is prime)
$ factor 170141183460469231731687303715884105697
170141183460469231731687303715884105697: 4347014963 39139774053837143815620977819


Speed

The coreutils version uses sophisticated number theory methods to speed things up, especially when all factors are small. Prime numbers are detected effectively instantaneously, but composite numbers with more than one large factor can take significant time to process. For instance, Xubuntu on a 4 GHz Core i7 shows

$ time factor $(echo 2^127-1 | bc)      # A prime number -- very fast
170141183460469231731687303715884105727: 170141183460469231731687303715884105727
real	0m0.005s
user	0m0.006s
sys	0m0.001s
$ time factor $(echo 2^127-305 | bc)    # A slightly smaller composite with 2 large factors - 2 minutes
170141183460469231731687303715884105423: 3 6490505778597245129 8737951980132681629
real	2m1.311s
user	2m1.300s
sys	0m0.000s
$ time factor $(echo 10^38+231 | bc)    # A somewhat smaller composite but with larger factors - 2.5 minutes
100000000000000000000000000000000000231: 9232227618290977207 10831622023906673233
real	2m31.258s
user	2m31.248s
sys	0m0.008s

Provided by

This command occurs in the GNU Coreutils where a man page can also be found. Many Linux systems, however, are using a different version. The current author has not yet tracked this down.


Related Commands

  • bc - arbitrary precision calculator language
  • dc - reverse-polish arbitrary precision calculator
  • seq - Show number sequences.