# Recipe 2.18 Program: Calculating Prime Factors

The following program takes one or more integer arguments and determines the prime factors. It uses Perl's native numeric representation, unless those numbers use floating-point representation and thus lose accuracy. Otherwise (or if the program's -b switch is used), it uses the standard Math::BigInt library, thus allowing for huge numbers. However, it only loads this library if necessary. That's why we use require and import instead of use, which would unconditionally load the library at compile time instead of conditionally at runtime. This is not an efficient way to crack the huge integers used for cryptographic purposes.

Call the program with a list of numbers, and it will show you the prime factors of those numbers:

```% bigfact 8 9 96 2178
8          2**3
9          3**2
96         2**5 3
2178       2 3**2 11**2```

You can give it very large numbers:

```% bigfact 239322000000000000000000
+239322000000000000000000 2**19 3 5**18 +39887

% bigfact 25000000000000000000000000
+25000000000000000000000000 2**24 5**26```

The program is shown in Example 2-2.

##### Example 2-2. bigfact
```  #!/usr/bin/perl
# bigfact - calculate prime factors
use strict;
use integer;

our (\$opt_b, \$opt_d);
use Getopt::Std;

@ARGV && getopts('bd')        or die "usage: \$0 [-b] number ...";

ARG: foreach my \$orig ( @ARGV ) {
my (\$n, %factors, \$factor);
\$n = \$opt_b ? Math::BigInt->new(\$orig) : \$orig;
if (\$n + 0 ne \$n) { # don't use -w for this
printf STDERR "bigfact: %s would become %s\n", \$n, \$n+0 if \$opt_d;
\$n = Math::BigInt->new(\$orig);
}
printf "%-10s ", \$n;

# Here \$sqi will be the square of \$i. We will take advantage
# of the fact that (\$i + 1) ** 2 =  = \$i ** 2 + 2 * \$i + 1.
for (my (\$i, \$sqi) = (2, 4); \$sqi <= \$n; \$sqi += 2 * \$i ++ + 1) {
while (\$n % \$i =  = 0) {
\$n /= \$i;
print STDERR "<\$i>" if \$opt_d;
\$factors {\$i} ++;
}
}

if (\$n != 1 && \$n != \$orig) { \$factors{\$n}++ }
if (! %factors) {
print "PRIME\n";
next ARG;
}
for \$factor ( sort { \$a <=> \$b } keys %factors ) {
print "\$factor";
if (\$factors{\$factor} > 1) {
print "**\$factors{\$factor}";
}
print " ";
}
print "\n";
}

# this simulates a use, but at runtime
require Math::BigInt;
Math::BigInt->import( );          #immaterial?
}```

 Chapter 1. Strings
 Chapter 3. Dates and Times
 Chapter 4. Arrays
 Chapter 5. Hashes
 Chapter 6. Pattern Matching
 Chapter 7. File Access
 Chapter 8. File Contents
 Chapter 9. Directories
 Chapter 10. Subroutines
 Chapter 11. References and Records
 Chapter 12. Packages, Libraries, and Modules
 Chapter 13. Classes, Objects, and Ties
 Chapter 14. Database Access
 Chapter 15. Interactivity
 Chapter 16. Process Management and Communication
 Chapter 17. Sockets
 Chapter 18. Internet Services
 Chapter 19. CGI Programming
 Chapter 20. Web Automation
 Chapter 21. mod_perl
 Chapter 22. XML