Factor
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.