home | O'Reilly's CD bookshelfs | FreeBSD | Linux | Cisco | Cisco Exam

## 2.18. Program: Calculating Prime Factors

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```

#### 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