Legendre prime counting function: Difference between revisions
Content deleted Content added
PicoLisp version |
|||
Line 819: | Line 819: | ||
writef("10^%w %w%n", K, pi(N)), |
writef("10^%w %w%n", K, pi(N)), |
||
N := N * 10. |
N := N * 10. |
||
</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) |
|||
</lang> |
</lang> |
||
{{Out}} |
{{Out}} |