sidef-scripts/Math/almost_prime_numbers_in_range.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 15 February 2021
# Edit: 13 March 2021
# https://github.com/trizen

# Generate k-almost prime numbers in range [a,b]. (not in sorted order)

# See also:
#   https://en.wikipedia.org/wiki/Almost_prime

func almost_prime_numbers(a, b, k, callback) {

    a = max(2**k, a)

    func (m, lo, k) {

        var hi = idiv(b,m).iroot(k)

        if (k == 1) {

            lo = max(lo, idiv_ceil(a, m))

            each_prime(lo, hi, {|p|
                callback(m*p)
            })

            return nil
        }

        each_prime(lo, hi, {|p|

            var t = m*p
            var u = idiv_ceil(a, t)
            var v = idiv(b, t)

            next if (u > v)    # optimization for tight ranges

            __FUNC__(t, p, k-1)
        })
    }(1, 2, k)

    return callback
}

# Generate 5-almost primes in the range [50, 1000]

var k    = 5
var from = 50
var upto = 1000

var arr = gather {
    almost_prime_numbers(from, upto, k, { take(_) })
}.sort

assert_eq(arr, from..upto -> grep{.is_almost_prime(k)})
say arr

# Run some more tests

for k in (1..10) {

    var from = k.pn_primorial.irand+1e3.irand
    var upto = from+1e3.irand

    say "Testing: k = #{k} with #{from} .. #{upto}"

    var arr = gather {
        almost_prime_numbers(from, upto, k, { take(_) })
    }.sort

    assert_eq(arr, max(from, 2**k)..upto -> grep{.is_almost_prime(k)})
}