n-smooth   numbers are positive integers which have no prime factors  >  n.

The   n   (when using it in the expression)   n-smooth   is always prime,

there are   no   9-smooth numbers.

1   (unity)   is always included in n-smooth numbers.




2-smooth   numbers are non-negative powers of two.

5-smooth   numbers are also called   Hamming numbers.

7-smooth   numbers are also called    humble   numbers.



A way to express   11-smooth   numbers is:

  11-smooth  =  2i × 3j × 5k × 7m × 11p

           where     i, j, k, m, p ≥ 0  



Task

   calculate and show the first   25   n-smooth numbers   for   n=2   ───►   n=29
   calculate and show   three numbers starting with   3,000   n-smooth numbers   for   n=3   ───►   n=29
   calculate and show twenty numbers starting with  30,000   n-smooth numbers   for   n=503   ───►   n=521   (optional)


All ranges   (for   n)   are to be inclusive, and only prime numbers are to be used.

The (optional) n-smooth numbers for the third range are:   503,   509,   and   521.

Show all n-smooth numbers for any particular   n   in a horizontal list.

Show all output here on this page.



Related tasks

   Hamming numbers
   humble numbers


References

   Wikipedia entry:   Hamming numbers     (this link is re-directed to   Regular number).
   Wikipedia entry:   Smooth number
   OEIS entry:   A000079    2-smooth numbers or non-negative powers of two
   OEIS entry:   A003586    3-smooth numbers
   OEIS entry:   A051037    5-smooth numbers or Hamming numbers
   OEIS entry:   A002473    7-smooth numbers or humble numbers
   OEIS entry:   A051038   11-smooth numbers
   OEIS entry:   A080197   13-smooth numbers
   OEIS entry:   A080681   17-smooth numbers
   OEIS entry:   A080682   19-smooth numbers
   OEIS entry:   A080683   23-smooth numbers


import sequtils, strutils
import bignum
 
const N = 521
 
 
func initPrimes(): tuple[primes: seq[Int]; smallPrimes: seq[int]] =
 
  var sieve: array[2..N, bool]
  for n in 2..N:
    if not sieve[n]:
      for k in countup(n * n, N, n): sieve[k] = true
 
  for n, isComposite in sieve:
    if not isComposite:
      result.primes.add newInt(n)
      if n <= 29: result.smallPrimes.add n
 
# Cache all primes up to N.
let (Primes, SmallPrimes) = initPrimes()
 
 
 
proc nSmooth(n, size: Positive): seq[Int] =
  assert n in 2..N, "'n' must be between 2 and " & $N
 
  let bn = newInt(n)
  assert bn in Primes, "'n' must be a prime number"
 
  result.setLen(size)
  result[0] = newInt(1)
 
  var next: seq[Int]
  for prime in Primes:
    if prime > bn: break
    next.add prime
 
  var indices = newSeq[int](next.len)
  for m in 1..<size:
    result[m] = next[next.minIndex()]
    for i in 0..indices.high:
      if result[m] == next[i]:
        inc indices[i]
        next[i] = Primes[i] * result[indices[i]]
 
 
when isMainModule:
 
  for n in SmallPrimes:
    echo "The first ", n, "-smooth numbers are:"
    echo nSmooth(n, 25).join(" ")
    echo ""
 
  for n in SmallPrimes[1..^1]:
    echo "The 3000th to 3202th ", n, "-smooth numbers are:"
    echo nSmooth(n, 3002)[2999..^1].join(" ")
    echo ""
 
  for n in [503, 509, 521]:
    echo "The 30000th to 30019th ", n, "-smooth numbers are:"
    echo nSmooth(n, 30_019)[29_999..^1].join(" ")
    echo ""