2.19. 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 floatingpoint 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 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 You can give it very large numbers: % bigfact 239322000000000000000000 The program is shown in Example 2.1 . Example 2.1: bigfact#!/usr/bin/perl # bigfact  calculate prime factors use strict; use integer; use vars qw{ $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 run time sub load_biglib { require Math::BigInt; Math::BigInt>import(); #immaterial? }
Copyright © 2002 O'Reilly & Associates. All rights reserved. 
