C++: Hamming Numbers

Hamming numbers are numbers of the form

$H = 2^i \cdot 3^j \cdot 5^k, \; \mathrm{where} \; i, j, k \geq 0$ .

Hamming numbers are also known as ugly numbers and also 5-smooth numbers (numbers whose prime divisors are less or equal to 5).

Generate the sequence of Hamming numbers, in increasing order. In particular:

Show the first twenty Hamming numbers.
Show the 1691st Hamming number (the last one below $231$ ).
Show the one millionth Hamming number (if the language – or a convenient library – supports arbitrary-precision integers).

C++11 For Each Generator

#include <iostream>
#include <vector>
// Hamming like sequences Generator
//
// Nigel Galloway. August 13th., 2012
//
class Ham {
private:
	std::vector<unsigned int> _H, _hp, _hv, _x;
public:
	bool operator!=(const Ham& other) const {return true;}
	Ham begin() const {return *this;}
	Ham end() const {return *this;}
	unsigned int operator*() const {return _x.back();}
	Ham(const std::vector<unsigned int> &pfs):_H(pfs),_hp(pfs.size(),0),_hv({pfs}),_x({1}){}
	const Ham& operator++() {
		for (int i=0; i<_H.size(); i++) for (;_hv[i]<=_x.back();_hv[i]=_x[++_hp[i]]*_H[i]);
		_x.push_back(_hv[0]);
		for (int i=1; i<_H.size(); i++) if (_hv[i]<_x.back()) _x.back()=_hv[i];
		return *this;
	}
};

5-Smooth

int main() {
	int count = 1;
	for (unsigned int i : Ham({2,3,5})) {
		if (count <= 62) std::cout << i << ' ';
		if (count++ == 1691) {
			std::cout << "\nThe one thousand six hundred and ninety first Hamming Number is " << i << std::endl;
			break;
		}
	}
	return 0;
}

Produces:

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 160 162 180 192 200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400 405
The one thousand six hundred and ninety first Hamming Number is 2125764000

7-Smooth

int main() {
	int count = 1;
	for (unsigned int i : Ham({2,3,5,7})) {
		std::cout << i << ' ';
		if (count++ == 64) break;
	}
	std::cout << std::endl;
	return 0;
}

Produces:

1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120 125 126 128 135 140 144 147 150 160 162 168 175 180 189

SOURCE

Content is available under GNU Free Documentation License 1.2.