Post date: Jul 12, 2013 6:25:31 AM
Problem
Design an algorithm to find the kth number divisible by only 3 or 5 or 7
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the kth number divisible by only 3 or 5 or 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 KthNumOnlyDivisibleBy357(int k)
{
int factor3(0), factor5(0), factor7(0);
vector<int> v;
while(v.size() <= (unsigned)k + 1)
{
int m = min3(factor3 + 3, factor5 + 5, factor7 + 7);
if(m % 105 == 0) factor3 = factor5 = factor7 = m;
else if(m % 35 == 0) factor5 = factor7 = m;
else if(m % 21 == 0) factor3 = factor7 = m;
else if(m % 15 == 0) factor3 = factor5 = m;
else{
if(m % 3 == 0) factor3 += 3;
if(m % 5 == 0) factor5 += 5;
if(m % 7 == 0) factor7 += 7;
v.push_back(m);
}
}
return v[k];
}
int main(int argc, char* argv[])
{
for(int i = 0; i < 25; ++i){
cout << i << "th ---- ";
cout << KthNumOnlyDivisibleBy357(i) << endl;
}
return 0;
}
Output
0th ---- 3
1th ---- 5
2th ---- 6
3th ---- 7
4th ---- 9
5th ---- 10
6th ---- 12
7th ---- 14
8th ---- 18
9th ---- 20
10th ---- 24
11th ---- 25
12th ---- 27
13th ---- 28
14th ---- 33
15th ---- 36
16th ---- 39
17th ---- 40
18th ---- 48
19th ---- 49
20th ---- 50
21th ---- 51
22th ---- 54
23th ---- 55
24th ---- 56
Press any key to continue . . .