44 lines
841 B
Text
44 lines
841 B
Text
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))
|