Perl Cd Bookshelf [Electronic resources] نسخه متنی

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 ...";
load_biglib( ) if $opt_b;
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;
load_biglib( );
$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
sub load_biglib {
require Math::BigInt;
Math::BigInt->import( );          #immaterial?
}