count_of_primes.sf

#!/usr/bin/ruby

# Sublinear algorithm for counting the number of primes <= n.

# Based on algorithm from:
#   https://math.stackexchange.com/questions/1378286/find-the-sum-of-all-primes-smaller-than-a-big-number

func count_of_primes(n) {

    return 0 if (n <= 1)

    var r = n.isqrt
    var V = (1..r -> map {|k| idiv(n,k) })
    V << range(V.last-1, 1, -1).to_a...

    var S = Hash(V.map{|k| (k, k) }...)

    for p in (2..r) {
        S{p} > S{p-1} || next
        var sp = S{p-1}
        var p2 = p*p
        V.each {|v|
            break if (v < p2)
            S{v} -= (S{idiv(v,p)} - sp)
        }
    }

    return S{n}-1
}

assert_eq(
    30.of { count_of_primes(_) }
    30.of { .pi }
)

say count_of_primes(1e6)    #=> 78498