Anonymous user
Count in factors: Difference between revisions
m
→{{header|Perl}}: Add another PP example and two quick module solutions. Edit joining text as needed, noting that the most interesting differences come with large inputs.
(→{{header|Perl}}: Added faster implementation.) |
m (→{{header|Perl}}: Add another PP example and two quick module solutions. Edit joining text as needed, noting that the most interesting differences come with large inputs.) |
||
Line 1,634:
=={{header|Perl}}==
Using the second extensible sieve from [[Sieve_of_Eratosthenes#Extensible_sieves]]. This is fairly fast and low memory for large inputs.
<lang perl>tie my @primes, 'Tie::SieveOfEratosthenes';
sub factors {
my($n, $i, $p, @out) = (shift, 0, 2);
while ($n >= $p * $p) {
while ($n % $p == 0) {
push @out, $p;
$n /= $p;
}
$p = $primes[++$i];
}
push @out, $n if $n > 1 || !@out;
@out;
}
print "$_ = ", join(" x ", factors($_)), "\n" for 100000000000 .. 100000000010;</lang>
{{out}}
<pre>100000000000 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5
100000000001 = 11 x 11 x 23 x 4093 x 8779
100000000002 = 2 x 3 x 7 x 1543 x 1543067
100000000003 = 100000000003
100000000004 = 2 x 2 x 17573 x 1422637
100000000005 = 3 x 5 x 19 x 1627 x 215659
100000000006 = 2 x 3947 x 12667849
100000000007 = 353 x 283286119
100000000008 = 2 x 2 x 2 x 3 x 3 x 3 x 462962963
100000000009 = 7 x 13 x 53 x 1979 x 10477
100000000010 = 2 x 5 x 101 x 3541 x 27961</pre>
This example isn't quite as fast and uses much more memory, but it is self-contained. As written it must start at 1, but a range can be handled by using a <code>map</code> to prefill the <tt>p_and_sq</tt> array.
<lang perl>#!perl -C
use utf8;
use strict;
use warnings;
my $limit = 1000;
print "$_ = $_\n" for 1..3;
Line 1,665 ⟶ 1,698:
}
</lang>
Another solution, quite slow for larger inputs.
<lang perl>use utf8;
Line 1,692 ⟶ 1,727:
print "$_ = ", join(" × ", factors($_)), "\n" for (1 .. 1000);</lang>
Lastly, we can use a module. Note that 1 returns no factors unlike the previous code which special cases it. These should be efficient through 50 or so digits.
<lang perl>use Math::Prime::Util qw/factor/;
print "$_ = ", join(" x ", factor($_)), "\n" for 1000000000000000000 .. 1000000000000000010;</lang>
or
<lang perl>use Math::Pari qw/factorint/;
sub factor {
my ($pn,$pc) = @{Math::Pari::factorint(shift)};
return map { ($pn->[$_]) x $pc->[$_] } 0 .. $#$pn;
}
print "$_ = ", join(" x ", factor($_)), "\n" for 1000000000000000000 .. 1000000000000000010;</lang>
{{out}}
<pre>1000000000000000000 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5
1000000000000000001 = 101 x 9901 x 999999000001
1000000000000000002 = 2 x 3 x 17 x 131 x 1427 x 52445056723
1000000000000000003 = 1000000000000000003
1000000000000000004 = 2 x 2 x 1801 x 246809 x 562425889
1000000000000000005 = 3 x 5 x 44087 x 691381 x 2187161
1000000000000000006 = 2 x 7 x 919 x 77724234416291
1000000000000000007 = 1370531 x 729644203597
1000000000000000008 = 2 x 2 x 2 x 3 x 3 x 97 x 26209 x 32779 x 166667
1000000000000000009 = 1000000000000000009
1000000000000000010 = 2 x 5 x 11 x 103 x 4013 x 21993833369</pre>
=={{header|Perl 6}}==
| |||