Anonymous user
Legendre prime counting function: Difference between revisions
→{{header|Python}}
m (J: a note of explanation) |
|||
Line 833:
10^9 50847534
</pre>
=={{header|Python}}==
Using <code>primesieve</code> module (<code>pip install primesieve</code>).
<lang python>from primesieve import primes
from math import isqrt
from functools import cache
p = primes(isqrt(1_000_000_000))
@cache
def phi(x, a):
res = 0
while True:
if not a or not x:
return x + res
a -= 1
res -= phi(x//p[a], a) # partial tail recursion
def legpi(n):
if n < 2: return 0
a = legpi(isqrt(n))
return phi(n, a) + a - 1
for e in range(10):
print(f'10^{e}', legpi(10**e))</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|Raku}}==
| |||