24 lines
523 B
Text
24 lines
523 B
Text
|
import "./math" for Int
|
||
|
|
|
||
|
|
var pi = Fn.new { |n|
|
||
|
|
if (n < 3) return (n < 2) ? 0 : 1
|
||
|
|
var primes = Int.primeSieve(n.sqrt.floor)
|
||
|
|
var a = primes.count
|
||
|
|
|
||
|
|
var phi // recursive closure
|
||
|
|
phi = Fn.new { |x, a|
|
||
|
|
if (a <= 1) return (a < 1) ? x : x - (x >> 1)
|
||
|
|
var pa = primes[a-1]
|
||
|
|
if (x <= pa) return 1
|
||
|
|
return phi.call(x, a-1) - phi.call((x/pa).floor, a-1)
|
||
|
|
}
|
||
|
|
|
||
|
|
return phi.call(n, a) + a - 1
|
||
|
|
}
|
||
|
|
|
||
|
|
var n = 1
|
||
|
|
for (i in 0..9) {
|
||
|
|
System.print("10^%(i) %(pi.call(n))")
|
||
|
|
n = n * 10
|
||
|
|
}
|