The following algorithm and source code may not be highly optimized to find the next highest number of the general form (2^a * 3^b * 5^c * 7^d), but it is useful in that the code will return the highest number with one of these powers.
The algorithm first checks if the number is a power of {2,3,5,7}. If it is, then the number is simply returned. If not, then the algorithm finds the smallest power that is higher than the input number.
More sophisticated methods would use prime-factorization
algorithms and searching/sorting, or perhaps a hard-coded look-up table,
but these solutions may be too complex for this application.
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
// http://stackoverflow.com/questions/1804311/how-to-check-if-an-integer-is-power-of-3
// Checks if n^x
int powerOf(int n, int x)
{
while (n % x == 0)
{
n /= x;
}
return n == 1;
}
unsigned int hN(unsigned int x, unsigned int base)
{
double exponent = std::ceil( std::log(x) / std::log(base) );
double num = std::pow(base, exponent);
return static_cast<unsigned int>(num);
}
unsigned int getHigherNumber(unsigned int n)
{
unsigned int rv = n;
const int pnum = 4;
// 1) Is the number a power of {2,3,5,7}?
// If it is, then simply return it
if(powerOf(n,2)) return rv;
if(powerOf(n,3)) return rv;
if(powerOf(n,5)) return rv;
if(powerOf(n,7)) return rv;
// 2) If not, then find next highest power of {2,3,5,7} that is the smallest
// number higher than n
unsigned int num0 = hN(n, 2);
unsigned int num1 = hN(n, 3);
unsigned int num2 = hN(n, 5);
unsigned int num3 = hN(n, 7);
std::vector<unsigned int>v(pnum);
v[0] = num0;
v[1] = num1;
v[2] = num2;
v[3] = num3;
rv = *std::min_element(v.begin(),v.end());
// 3) TODO: More sophisticated methods would use prime-factorization
// algorithms and searching/sorting, or perhaps a look-up table,
// but these may be too complex for this application
return rv;
} // end
int main()
{
// const unsigned int num = 64;
// const unsigned int num = 18;
const unsigned int num = 2234;
std::cout << "num = " << num << std::endl;
std::cout << "higher number = " << getHigherNumber( num ) << std::endl;
} // end