[FIXED] How can i find the integers that can be written as a sum of a power of 2, a power of 3 and a power of 5? C++

Issue

So the program must compute all the numbers that can be written as a sum of a power of 2, a power of 3 and a power of 5 below 5.000.000. For example 42 = 16 + 1 + 25 = 2^4 + 3^0 + 5^2. Any idea how can I do this?

Solution

you can get all powers of 2 and all powers of 3 and all powers of 5 under 5.000.000. first
Then you can try all combinations

vector<int> solve(){
 const int M = 5000000;
 vector<int> p_2={1},p_3={1},p_5={1};
 while(p_2.back()*2<M)p_2.push_back(p_2.back()*2);
 while(p_3.back()*3<M)p_3.push_back(p_3.back()*3);
 while(p_5.back()*5<M)p_5.push_back(p_5.back()*5);
 set<int> st;//to remove duplicates
 for(auto power_of_2 :p_2){
     for(auto power_of_3:p_3){
         for(auto power_of_5:p_5){
            If(power_of_2+power_of_3+power_of_5<M)
             st.insert(power_of_2+power_of_3+power_of_5);
         }
     }
 }
 return vector<int>(st.begin(),st.end());
}

Answered By - Mohaned El-haddad

Answer Checked By - Mary Flores (PHPFixing Volunteer)