Legendre prime counting function: Difference between revisions

 

=={{header|C++}}==

#include <iostream>

#include <unordered_map>

for (int i = 0, n = 1; i < 10; ++i, n *= 10)

std::cout << "10^" << i << "\t" << counter.prime_count(n) << '\n';

 

{{out}}

 

=={{header|CoffeeScript}}==

sorenson = require('sieve').primes # Sorenson's extensible sieve from task: Extensible Prime Generator

 

console.log "10^#{i}\t#{pi(n)}"

n *= 10

{{Out}}

<pre>

</pre>

=={{header|Erlang}}==

-mode(native).

 

true -> M + 1

end.

{{Out}}

<pre>

 

The alternative of sieving a billion numbers and then counting them takes about 4.8 seconds using the present library function though this could be cut to 1.2 seconds using a third party library such as primegen.

 

import (

fmt.Printf("10^%d %d\n", i, pi(n))

}

 

{{out}}

 

=={{header|Java}}==

 

public class LegendrePrimeCounter {

return primes;

}

 

{{out}}

 

Memoization utilities:

deriving Functor

 

split [] = ([],[])

split [x] = ([x],[])

 

Computation of Legendre function:

isqrt n = go n 0 (q `shiftR` 2)

where

where a = legendrePi (floor (sqrt (fromInteger n)))

 

 

<pre>λ> main

This is "almost a primitive" in J:

 

{{echo '10^%d: %d' sprintf y;p:inv 10^y}}"0 i.10

10^0: 0

10^7: 664579

10^8: 5761455

 

A complete implementation of the legendre prime counting function would be <tt>(1&p: + p:inv)</tt>:

 

4

(1&p: + p:inv) 11

 

But we can simplify that to p:inv when we know that primes are not being tested.

 

'''Preliminaries'''

def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);

 

| reduce (2, 1 + (2 * range(1; $s))) as $i (.; erase($i))

| map(select(.)) ;

'''Phi and the Legendre Counting Function'''

(sqrt | floor + 1 | eratosthenes) as $primes

 

;

 

 

{{out}}

=== Using the Julia Primes library ===

This would be faster with a custom sieve that only counted instead of making a bitset, instead of the more versatile library function.

 

function primepi(N)

println("10^", rpad(power, 5), primepi(10^power))

end

<pre>

10^0 0

{{trans|CoffeeScript}}

Run twice to show the benefits of precomputing the library prime functions.

 

const maxpi = 1_000_000_000

end

 

<pre>

10^0 1

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

$RecursionLimit = 10^6;

Phi[x_, 0] := x

Phi[x_, a_] := Phi[x, a] = Phi[x, a - 1] - Phi[Floor[x/Prime[a]], a - 1]

pi[n_] := Module[{a}, If[n < 2, 0, a = pi[Floor[Sqrt[n]]]; Phi[n, a] + a - 1]]

{{out}}

<pre>0

=={{header|Nim}}==

The program runs in 2.2 seconds on our laptop. Using int32 instead of naturals (64 bits on our 64 bits computer) saves 0.3 second. Using an integer rather than a tuple as key (for instance <code>x shl 32 or a</code>) saves 0.4 second.

 

const

for i in 0..9:

echo "π(10^$1) = $2".format(i, π(n))

 

{{out}}

 

=={{header|Perl}}==

 

use strict; # https://rosettacode.org/wiki/Legendre_prime_counting_function

{

printf "%d %12d %10d %10d\n", $_, 10**$_, pi(10**$_), prime_count(10**$_);

{{out}}

<pre>

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #000080;font-style:italic;">--

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>

The commented-out length(get_primes_le()) gives the same results, in about the same time,

and in both cases re-running the main loop a second time finishes near-instantly.

=={{header|Picat}}==

Performance is surprisingly good, considering that the Picat's library SoE is very basic and that I recompute the base primes each time pi() is called. This version takes 23 seconds on my laptop, outperforming the CoffeeScript version which takes 30 seconds.

table(+, +, nt)

phi(X, 0, _) = X.

writef("10^%w %w%n", K, pi(N)),

N := N * 10.

{{Out}}

<pre>

=={{header|PicoLisp}}==

Uses code from the Sieve of Eratosthenes to generate primes.

(setq Legendre-Max (** 10 9))

 

 

(bye)

{{Out}}

<pre>

=={{header|Python}}==

Using <code>primesieve</code> module (<code>pip install primesieve</code>).

from math import isqrt

from functools import cache

 

for e in range(10):

{{out}}

<pre>10^0 0

=={{header|Raku}}==

Seems like an awful lot of pointless work. Using prime sieve anyway, why not just use it?

 

my $sieve = Math::Primesieve.new;

say "10^$_\t" ~ $sieve.count: exp($_,10) for ^10;

 

{{out}}

<pre>10^0 0

 

=={{header|Sidef}}==

return x if (a <= 0)

__FUNC__(x, a-1) - __FUNC__(idiv(x, a.prime), a-1)

legendre_prime_count(10**n), prime_count(10**n))

assert_eq(legendre_prime_count(10**n), prime_count(10**n))

{{out}}

<pre>

Alternative implementation of the Legendre phi function, by counting k-rough numbers <= n.

 

 

# Count of k-rough numbers <= n.

legendre_prime_count(10**n), prime_count(10**n))

assert_eq(legendre_prime_count(10**n), prime_count(10**n))

 

=={{header|Swift}}==

 

 

extension Numeric where Self: Strideable {

 

print("π(10^\(i)) = \(π(n: n))")

 

{{out}}

 

To sieve a billion numbers and then count the primes up to 10^k would take about 53 seconds in Wren so, as expected, the Legendre method represents a considerable speed up.

 

var limit = 1e9.sqrt.floor

System.print("10^%(i) %(pi.call(n))")

n = n * 10

 

{{out}}