Hamming numbers | Rosetta Code | #18
URL to the problem page: https://rosettacode.org/wiki/Hamming_numbers
Hamming numbers are numbers of the form
where
Hamming numbers are also known as ugly numbers and also 5-smooth numbers (numbers whose prime divisors are less or equal to 5).
Show the first twenty Hamming numbers.
Show the 1691st Hamming number (the last one below 231).
Hamming numbers are numbers of the form
- H = 2i × 3j × 5k
where
- i, j, k ≥ 0
Hamming numbers are also known as ugly numbers and also 5-smooth numbers (numbers whose prime divisors are less or equal to 5).
Show the first twenty Hamming numbers.
Show the 1691st Hamming number (the last one below 231).
#include <iostream>
using namespace std;
long long int power(int a, int b) {
long long int result = 1;
for (int i = 0; i < b; i++) {
result *= a;
}
return result;
}
int main()
{
int cnt, a = 0, tmp;
long long int numbers[20000] = { 0 }, smallest;
cout << "First 20 Hamming numbers are:" << endl;
for (int n = 0; a < 20000; n++) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++) {
if ((power(2, i) * power(3, j) * power(5, k)) > 0) {
cnt = 0;
for (int m = 0; m < a; m++) {
if (numbers[m] == (power(2, i) * power(3, j) * power(5, k))) {
cnt++;
break;
}
}
if (cnt == 0) {
numbers[a] = (power(2, i) * power(3, j) * power(5, k));
a++;
}
if (a == 20000) {
break;
}
}
}
if (a == 20000) {
break;
}
}
if (a == 20000) {
break;
}
}
}
for (int i = 0; i < a; i++) {
smallest = numbers[i];
tmp = i;
for (int j = i + 1; j < a; j++) {
if (numbers[j] < smallest) {
smallest = numbers[j];
tmp = j;
}
}
numbers[tmp] = numbers[i];
numbers[i] = smallest;
if (i < 20) {
cout << numbers[i] << ", ";
}
else if (i == 1690) {
cout << endl << endl << "1691st Hamming number (the last one below 2^31) is = " << numbers[i] << endl;
}
}
return 0;
}
Comments
Post a Comment