Sub primeSieve(limit As Uinteger, primes() As Uinteger)
    Dim As Uinteger i, j
    Dim As Uinteger sieve(limit)

    For i = 2 To limit
        sieve(i) = 1
    Next

    For i = 2 To limit
        If sieve(i) Then
            Redim Preserve primes(Ubound(primes) + 1)
            primes(Ubound(primes)) = i
            For j = i * i To limit Step i
                sieve(j) = 0
            Next
        End If
    Next
End Sub

Function phi(x As Uinteger, a As Uinteger, primes() As Uinteger) As Uinteger
    If a <= 1 Then Return Iif(a < 1, x, x - (x \ 2))

    Dim As Uinteger pa = primes(a - 1)
    If x <= pa Then Return 1

    Return phi(x, a - 1, primes()) - phi(x \ pa, a - 1, primes())
End Function

Function pi(n As Uinteger) As Uinteger
    If n < 3 Then Return Iif(n < 2, 0, 1)

    Dim As Uinteger primes()
    primeSieve(Int(Sqr(n)), primes())

    Dim As Uinteger a = Ubound(primes) + 1
    Return phi(n, a, primes()) + a - 1
End Function

Dim As Uinteger i, n = 1
For i = 0 To 9
    Print "10^" & i & "  " & pi(n)
    n *= 10
Next

Sleep