Legendre prime counting function: Difference between revisions
Content added Content deleted
m (→{{header|C}}: Aligned with VLang.) |
Alextretyak (talk | contribs) (Added 11l) |
||
| Line 33: | Line 33: | ||
<br> |
<br> |
||
<br> |
<br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l"> |
|||
F primes_up_to_limit(Int limit) |
|||
[Int] r |
|||
I limit >= 2 |
|||
r.append(2) |
|||
V isprime = [1B] * ((limit - 1) I/ 2) |
|||
V sieveend = Int(sqrt(limit)) |
|||
L(i) 0 .< isprime.len |
|||
I isprime[i] |
|||
Int p = i * 2 + 3 |
|||
r.append(p) |
|||
I i <= sieveend |
|||
L(j) ((p * p - 3) >> 1 .< isprime.len).step(p) |
|||
isprime[j] = 0B |
|||
R r |
|||
V p = primes_up_to_limit(Int(sqrt(1'000'000'000))) |
|||
F phi(x, =a) |
|||
F phi_cached(x, a) |
|||
[(Int, Int) = Int] :cache |
|||
I (x, a) C :cache |
|||
R :cache[(x, a)] |
|||
V r = phi(x, a) |
|||
:cache[(x, a)] = r |
|||
R r |
|||
V res = 0 |
|||
L |
|||
I a == 0 | x == 0 |
|||
R x + res |
|||
a-- |
|||
res -= phi_cached(x I/ :p[a], a) |
|||
F legpi(n) |
|||
I n < 2 |
|||
R 0 |
|||
V a = legpi(Int(sqrt(n))) |
|||
R phi(n, a) + a - 1 |
|||
L(e) 10 |
|||
print(‘10^’e‘ ’legpi(10 ^ e)) |
|||
</syntaxhighlight> |
|||
{{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|C}}== |
=={{header|C}}== |
||