Function smooth_numbers::smooth

pub fn smooth(k: usize, n: usize) -> Vec<u64>

Generates the first n k-smooth numbers, i.e. numbers whose prime factors are smaller than or equal to k.

See the definition of smooth number on Wikipedia and MathWorld.

Examples

With k < 2, the numbers cannot have any prime factor, hence the only smooth number in this case is 1.

assert_eq!(smooth(0, 0), []);
assert_eq!(smooth(0, 1), [1]);
assert_eq!(smooth(0, 10), [1]);
assert_eq!(smooth(1, 10), [1]);

With k == 2, the numbers can only have the prime factor 2, hence we obtain the sequence of the powers of 2.

assert_eq!(smooth(2, 10), [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]);

With k == 3, the numbers can only have the prime factors 2 and 3, hence we obtain the sequence of the numbers of the form 2^i * 3^j, also known as Pratt’s sequence. See the pratt function for a specialized algorithm to generate this sequence.

assert_eq!(smooth(3, 10), [1, 2, 3, 4, 6, 8, 9, 12, 16, 18]);