Problem
Given an equation in the form 2^i * 3^j * 5^k * 7^l where i,j,k,l >=0 are integers.write a program to generate numbers from that equation in sorted order efficiently.
for example numbers from that equation will be in the order 2,3,5,6,7,8,9.....and so on..
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Generate numbers from 2^i * 3^j * 5^k * 7^l in sorted order.
Created Date : 1-August-2013
Last Modified :
===========================================================================
*/
#include <queue>
#include <vector>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <cassert>
#include <functional>
using namespace std;
using namespace stdext;
void GenerateNumbers(int n, vector<int>& output)
{
assert(n > 0);
int arr[] = {2, 3, 5, 7};
priority_queue<int, vector<int>, greater<int> > q(arr, arr + sizeof(arr)/sizeof(arr[0]));
int prev = 0;
while(output.size() < n){
int m = q.top();
q.pop();
if(prev != m){
output.push_back(m);
for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++){
q.push(m * arr[i]);
}
}
prev = m;
}
}
int main(int argc, char* argv[])
{
vector<int> output;
GenerateNumbers(1, output);
cout << "Generate 1 element " << endl;
copy(output.begin(), output.end(), ostream_iterator<int>(cout, " "));
cout << "\n----------------------------" << endl;
output.clear();
GenerateNumbers(15, output);
cout << "Generate 15 elements " << endl;
copy(output.begin(), output.end(), ostream_iterator<int>(cout, " "));
cout << "\n----------------------------" << endl;
output.clear();
GenerateNumbers(25, output);
cout << "Generate 25 elements " << endl;
copy(output.begin(), output.end(), ostream_iterator<int>(cout, " "));
cout << "\n----------------------------" << endl;
return 0;
}
Output
Generate 1 element
2
----------------------------
Generate 15 elements
2 3 4 5 6 7 8 9 10 12 14 15 16 18 20
----------------------------
Generate 25 elements
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
----------------------------
Press any key to continue . . .