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


fn is_prime(n: u32) -> bool {
    if n < 2 {
        return false;
    }
    if n % 2 == 0 {
        return n == 2;
    }
    if n % 3 == 0 {
        return n == 3;
    }
    let mut p = 5;
    while p * p <= n {
        if n % p == 0 {
            return false;
        }
        p += 2;
        if n % p == 0 {
            return false;
        }
        p += 4;
    }
    true
}
 
fn find_primes(from: u32, to: u32) -> Vec<u32> {
    let mut primes: Vec<u32> = Vec::new();
    for p in from..=to {
        if is_prime(p) {
            primes.push(p);
        }
    }
    primes
}
 
fn find_nsmooth_numbers(n: u32, count: usize) -> Vec<u128> {
    let primes = find_primes(2, n);
    let num_primes = primes.len();
    let mut result = Vec::with_capacity(count);
    let mut queue = Vec::with_capacity(num_primes);
    let mut index = Vec::with_capacity(num_primes);
    for i in 0..num_primes {
        index.push(0);
        queue.push(primes[i] as u128);
    }
    result.push(1);
    for i in 1..count {
        for p in 0..num_primes {
            if queue[p] == result[i - 1] {
                index[p] += 1;
                queue[p] = result[index[p]] * primes[p] as u128;
            }
        }
        let mut min_index: usize = 0;
        for p in 1..num_primes {
            if queue[min_index] > queue[p] {
                min_index = p;
            }
        }
        result.push(queue[min_index]);
    }
    result
}
 
fn print_nsmooth_numbers(n: u32, begin: usize, count: usize) {
    let numbers = find_nsmooth_numbers(n, begin + count);
    print!("{}: {}", n, &numbers[begin]);
    for i in 1..count {
        print!(", {}", &numbers[begin + i]);
    }
    println!();
}
 
fn main() {
    println!("First 25 n-smooth numbers for n = 2 -> 29:");
    for n in 2..=29 {
        if is_prime(n) {
            print_nsmooth_numbers(n, 0, 25);
        }
    }
    println!();
    println!("3 n-smooth numbers starting from 3000th for n = 3 -> 29:");
    for n in 3..=29 {
        if is_prime(n) {
            print_nsmooth_numbers(n, 2999, 3);
        }
    }
    println!();
    println!("20 n-smooth numbers starting from 30,000th for n = 503 -> 521:");
    for n in 503..=521 {
        if is_prime(n) {
            print_nsmooth_numbers(n, 29999, 20);
        }
    }
}