ЭЛЕКТРОННАЯ БИБЛИОТЕКА КОАПП |
Сборники Художественной, Технической, Справочной, Английской, Нормативной, Исторической, и др. литературы. |
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(); }
|