Legendre prime counting function: Difference between revisions

</lang>

{{Out}}

<pre>

10^0 0

10^1 4

10^2 25

10^3 168

10^4 1229

10^5 9592

10^6 78498

10^7 664579

10^8 5761455

10^9 50847534

</pre>

=={{header|PicoLisp}}==

Uses code from the Sieve of Eratosthenes to generate primes.

<lang PicoLisp>

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

(load "plcommon/eratosthenes.l") # see task "Sieve of Eratosthenes, 2x3x5x7 wheel version.

# Create an index tree of the first N primes up to √Legendre-Max

(setq Sieve (sieve (sqrt Legendre-Max)))

(balance 'Primes (mapcar 'cons (range 1 (length Sieve)) Sieve))

(de prime (N) (cdr (lup Primes N)))

(de ϕ (X A)

(cache '(NIL) (cons X A)

(if (=0 A)

X

(- (ϕ X (dec A)) (ϕ (/ X (prime A)) (dec A))))))

(de π (N)

(if (< N 2)

0

(let A (π (sqrt N))

(+ (ϕ N A) A -1))))

(for N 10

(prinl "10\^" (dec N) "^I" (π (** 10 (dec N)))))

(bye)