📄 ch02_20.htm
字号:
<HTML><HEAD><TITLE>Recipe 2.19. Program: Calculating Prime Factors (Perl Cookbook)</TITLE><METANAME="DC.title"CONTENT="Perl Cookbook"><METANAME="DC.creator"CONTENT="Tom Christiansen & Nathan Torkington"><METANAME="DC.publisher"CONTENT="O'Reilly & Associates, Inc."><METANAME="DC.date"CONTENT="1999-07-02T01:30:26Z"><METANAME="DC.type"CONTENT="Text.Monograph"><METANAME="DC.format"CONTENT="text/html"SCHEME="MIME"><METANAME="DC.source"CONTENT="1-56592-243-3"SCHEME="ISBN"><METANAME="DC.language"CONTENT="en-US"><METANAME="generator"CONTENT="Jade 1.1/O'Reilly DocBook 3.0 to HTML 4.0"><LINKREV="made"HREF="mailto:online-books@oreilly.com"TITLE="Online Books Comments"><LINKREL="up"HREF="ch02_01.htm"TITLE="2. Numbers"><LINKREL="prev"HREF="ch02_19.htm"TITLE="2.18. Printing Correct Plurals"><LINKREL="next"HREF="ch03_01.htm"TITLE="3. Dates and Times"></HEAD><BODYBGCOLOR="#FFFFFF"><img alt="Book Home" border="0" src="gifs/smbanner.gif" usemap="#banner-map" /><map name="banner-map"><area shape="rect" coords="1,-2,616,66" href="index.htm" alt="Perl Cookbook"><area shape="rect" coords="629,-11,726,25" href="jobjects/fsearch.htm" alt="Search this book" /></map><div class="navbar"><p><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch02_19.htm"TITLE="2.18. Printing Correct Plurals"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 2.18. Printing Correct Plurals"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><B><FONTFACE="ARIEL,HELVETICA,HELV,SANSERIF"SIZE="-1"><ACLASS="chapter"REL="up"HREF="ch02_01.htm"TITLE="2. Numbers"></A></FONT></B></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="chapter"HREF="ch03_01.htm"TITLE="3. Dates and Times"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 3. Dates and Times"BORDER="0"></A></TD></TR></TABLE></DIV><DIVCLASS="sect1"><H2CLASS="sect1"><ACLASS="title"NAME="ch02-chap02_program_0">2.19. Program: Calculating Prime Factors</A></H2><PCLASS="para"><ACLASS="indexterm"NAME="ch02-idx-1000008162-0"></A><ACLASS="indexterm"NAME="ch02-idx-1000008162-1"></A><ACLASS="indexterm"NAME="ch02-idx-1000008162-2"></A>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 <BCLASS="emphasis.bold">-b</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 <CODECLASS="literal">require</CODE> and <CODECLASS="literal">import</CODE> instead of <CODECLASS="literal">use</CODE>, which would unconditionally load the library at compile time instead of conditionally at run time.</P><PCLASS="para">This is not an efficient way to crack the huge integers used for cryptographic purposes.</P><PCLASS="para">Call the program with a list of numbers, and it will show you the prime factors of those numbers:</P><PRECLASS="programlisting">% bigfact 8 9 96 2178<CODECLASS="userinput"><B><CODECLASS="replaceable"><I>8 2**3</I></CODE></B></CODE><CODECLASS="userinput"><B><CODECLASS="replaceable"><I>9 3**2</I></CODE></B></CODE><CODECLASS="userinput"><B><CODECLASS="replaceable"><I>96 2**5 3</I></CODE></B></CODE><CODECLASS="userinput"><B><CODECLASS="replaceable"><I>2178 2 3**2 11**2</I></CODE></B></CODE></PRE><PCLASS="para">You can give it very large numbers:</P><PRECLASS="programlisting">% bigfact 239322000000000000000000<CODECLASS="userinput"><B><CODECLASS="replaceable"><I>+239322000000000000000000 2**19 3 5**18 +39887 </I></CODE></B></CODE>% bigfact 25000000000000000000000000<CODECLASS="userinput"><B><CODECLASS="replaceable"><I>+25000000000000000000000000 2**24 5**26</I></CODE></B></CODE></PRE><PCLASS="para">The program is shown in <ACLASS="xref"HREF="ch02_20.htm#ch02-24723"TITLE="bigfact">Example 2.1</A>.</P><DIVCLASS="example"><H4CLASS="example"><ACLASS="title"NAME="ch02-24723">Example 2.1: bigfact</A></H4><PRECLASS="programlisting">#!/usr/bin/perl# <ACLASS="indexterm"NAME="ch02-idx-1000008363-0"></A>bigfact - calculate prime factorsuse 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 timesub load_biglib { require Math::BigInt; Math::BigInt->import(); #immaterial?}<ACLASS="indexterm"NAME="ch02-idx-1000008164-0"></A><ACLASS="indexterm"NAME="ch02-idx-1000008164-1"></A><ACLASS="indexterm"NAME="ch02-idx-1000008164-2"></A></PRE></DIV><PRECLASS="programlisting"><ACLASS="indexterm"NAME="ch02-idx-1000007973-0"></A></PRE></DIV><DIVCLASS="htmlnav"><P></P><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch02_19.htm"TITLE="2.18. Printing Correct Plurals"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 2.18. Printing Correct Plurals"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="book"HREF="index.htm"TITLE="Perl Cookbook"><IMGSRC="../gifs/txthome.gif"ALT="Perl Cookbook"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="chapter"HREF="ch03_01.htm"TITLE="3. Dates and Times"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 3. Dates and Times"BORDER="0"></A></TD></TR><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228">2.18. Printing Correct Plurals</TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="index"HREF="index/index.htm"TITLE="Book Index"><IMGSRC="../gifs/index.gif"ALT="Book Index"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228">3. Dates and Times</TD></TR></TABLE><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><FONTSIZE="-1"></DIV<!-- LIBRARY NAV BAR --> <img src="../gifs/smnavbar.gif" usemap="#library-map" border="0" alt="Library Navigation Links"><p> <a href="copyrght.htm">Copyright © 2002</a> O'Reilly & Associates. All rights reserved.</font> </p> <map name="library-map"> <area shape="rect" coords="1,0,85,94" href="../index.htm"><area shape="rect" coords="86,1,178,103" href="../lwp/index.htm"><area shape="rect" coords="180,0,265,103" href="../lperl/index.htm"><area shape="rect" coords="267,0,353,105" href="../perlnut/index.htm"><area shape="rect" coords="354,1,446,115" href="../prog/index.htm"><area shape="rect" coords="448,0,526,132" href="../tk/index.htm"><area shape="rect" coords="528,1,615,119" href="../cookbook/index.htm"><area shape="rect" coords="617,0,690,135" href="../pxml/index.htm"></map> </BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -