Legendre prime counting function: Difference between revisions
Content added Content deleted
(Added Java solution) |
|||
Line 507: | Line 507: | ||
π(10^8) = 5761455 |
π(10^8) = 5761455 |
||
π(10^9) = 50847534</pre> |
π(10^9) = 50847534</pre> |
||
=={{header|Perl}}== |
|||
<lang perl>#!/usr/bin/perl |
|||
use strict; # https://rosettacode.org/wiki/Legendre_prime_counting_function |
|||
use warnings; |
|||
no warnings qw(recursion); |
|||
use ntheory qw( nth_prime prime_count ); |
|||
my (%cachephi, %cachepi); |
|||
sub phi |
|||
{ |
|||
return $cachephi{"@_"} //= do { |
|||
my ($x, $aa) = @_; |
|||
$aa <= 0 ? $x : phi($x, $aa - 1) - phi(int $x / nth_prime($aa), $aa - 1) }; |
|||
} |
|||
sub pi |
|||
{ |
|||
return $cachepi{$_[0]} //= do { |
|||
my $n = shift; |
|||
$n < 2 ? 0 : do{ my $aa = pi(int sqrt $n); phi($n, $aa) + $aa - 1 } }; |
|||
} |
|||
print "e n Legendre ntheory\n", |
|||
"- - -------- -------\n"; |
|||
for (1 .. 9) |
|||
{ |
|||
printf "%d %12d %10d %10d\n", $_, 10**$_, pi(10**$_), prime_count(10**$_); |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
e n Legendre ntheory |
|||
- - -------- ------- |
|||
1 10 4 4 |
|||
2 100 25 25 |
|||
3 1000 168 168 |
|||
4 10000 1229 1229 |
|||
5 100000 9592 9592 |
|||
6 1000000 78498 78498 |
|||
7 10000000 664579 664579 |
|||
8 100000000 5761455 5761455 |
|||
9 1000000000 50847534 50847534 |
|||
</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |