Приглашаем посетить
2.19. Программа: разложение на простые множители
Следующая программа получает один или несколько целых аргументов и раскладывает их на простые множители. В ней используется традиционное числовое представление Peri, кроме тех ситуаций, когда представление с плавающей запятой может привести к потере точности. В противном случае (или при запуске с параметром -Ь) используется стандартная библиотека Math:: Blight, что позволяет работать с большими числами. Однако библиотека загружается лишь при необходимости, поэтому вместо use используются ключевые слова require и import - это позволяет выполнить динамическую загрузку библиотеки во время выполнения вместо статической загрузки на стадии компиляции.
Наша программа недостаточно эффективна для подбора больших простых чисел, используемых в криптографии.
Запустите программу со списком чисел, и она выведет простые множители для каждого числа:
$ factors 8 9 96 2178
8 2**3
9 3**2
96 2**5 3
2178 2 3**2 11**2
Программа нормально работает и с очень большими числами:
% factors 239322000000000000000000 +239322000000000000000000 2**19 3 5**18 +39887 % factors 23932200000000000000000000 +25000000000000000000000000 2**24 5**26
Исходный текст программы приведен в примере 2.1.
Пример 2.1. bigfact
#!/usr/bin/peri
# bigfact - разложение на простые множители
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 ( OARGV ) {
my ($n, $root, %factors, $factor);
$n = $opt_b ? Math::BigInt->new($orig) : $orig;
if ($n + 0 ne $n) { ft don't use -w for this
printf STDERR "bignum: %s would become %s\n", $n, $n+0 if $opt_d;
load_biglib();
$n = math::bigint->new($orig);
} printf "%-10s ", $n;
# $sqi равно квадрату $i. Испильзууюя loi фак1, ft что ($i + 1) "* 2 == $l ** 2 + 2 * $i + 1.
for (my ($i, $sqi) = (2, 4); $sqi <= $n; $sqi += 2 * $i ++ + 1) { while ($n % $i == 0) {
$n /= $i:
print STDERR "" 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 "\r\";
}
# Имитирует use, но во время выполнения
sub load_biglib {
require Math::BigInt;
Math:;BigInt->import();
}
