Problem
Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.
1, 3, 5, 7, 3 * 3, 3 * 5, 3 *7, 5 * 5, 3 * 3 * 3, 5 * 7, 3 * 3 * 5, 7 * 7
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the kth number such that the only prime factors are 3, 5, and 7
Created Date : 12-July-2013
Last Modified :
===========================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
static inline int min3(int a, int b, int c)
{
return min(min(a, b), c);
}
static int KthFactorOf357(int k)
{
int count3(0), count5(0), count7(0);
vector<int> v;
v.push_back(1);
while(v.size() <= (unsigned)k + 1)
{
int m = min3(v[count3] * 3, v[count5] * 5, v[count7] * 7);
v.push_back(m);
if(m == v[count3] * 3) count3 ++;
if(m == v[count5] * 5) count5 ++;
if(m == v[count7] * 7) count7 ++;
}
return v[k];
}
int main(int argc, char* argv[])
{
for(int i = 0; i < 15; ++i){
cout << i << "th ---- ";
cout << KthFactorOf357(i) << endl;
}
return 0;
}
Output
0th ---- 1
1th ---- 3
2th ---- 5
3th ---- 7
4th ---- 9
5th ---- 15
6th ---- 21
7th ---- 25
8th ---- 27
9th ---- 35
10th ---- 45
11th ---- 49
12th ---- 63
13th ---- 75
14th ---- 81
Press any key to continue . . .