123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475 |
- #!/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)})
- }
|