#!/usr/bin/ruby

# A nice algorithm in terms of the prime-counting function for counting the number of prime powers <= n, with exponents >= 1.

# See also:
#   https://oeis.org/A025528
#   https://en.wikipedia.org/wiki/Prime-counting_function
#   https://trizenx.blogspot.com/2018/11/partial-sums-of-arithmetical-functions.html

# Example:
#    a(10^1)  = 7
#    a(10^2)  = 35
#    a(10^3)  = 193
#    a(10^4)  = 1280
#    a(10^5)  = 9700
#    a(10^6)  = 78734
#    a(10^7)  = 665134
#    a(10^8)  = 5762859
#    a(10^9)  = 50851223
#    a(10^10) = 455062595
#    a(10^11) = 4118082969
#    a(10^12) = 37607992088
#    a(10^13) = 346065767406
#    a(10^14) = 3204942420923
#    a(10^15) = 29844572385358

require('ntheory')

func my_pp_count(a, b) {

    if (b < a) {
        return 0
    }

    if (Num(Num.INTSIZE) > 32) {
        with (try { %S<ntheory>.prime_power_count(b) - %S<ntheory>.prime_power_count(a-1) }) {|v|
            return v
        }
    }

    if (a == 2) {
        return sum(1..b.ilog2, {|k|
            prime_count(b.iroot(k))
        })
    }

    var r = (__FUNC__(2, b) - __FUNC__(2, a))

    if (a.is_prime_power) {
        r += 1
    }

    return r
}


#~ func my_pp_count(a, b) {
    #~ a..b -> count_by { .is_prime_power }
#~ }

assert_eq(prime_power_count(11717, 388912), my_pp_count(11717, 388912))

for n in (1..1000) {

    var k = 1e9.irand
    var m = 1e10.irand

    say "Testing: #{k} (#{k.is_prime_power}) and #{m} (#{m.is_prime_power})"

    assert_eq(prime_power_count(k, m), my_pp_count(k, m))
}


__END__
for n in (1..15) {
    say "a(10^#{n}) = #{prime_power_count(10**n)}"
}
