project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_87.cpp (1217B)

      1 #include <iostream>
      2 #include <unordered_set>
      3 
      4 #include "Euler.h"
      5 
      6 uint64_t Euler::PrimePowerTriples()
      7 {
      8     //what is the upper bound?
      9     //bc <<< "84^4 < 50000000"
     10     //bc <<< "368^3 < 50000000"
     11     //bc <<< "7071^2 < 50000000"
     12 
     13     std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(7072);
     14     std::vector<uint64_t> cubes;
     15     std::vector<uint64_t> fourths;
     16     std::unordered_set<uint64_t> solutions;
     17 
     18     for (uint64_t i = 0; i < 369; ++i) {
     19           cubes.push_back(i * i * i);
     20           if (i < 85) {
     21               fourths.push_back(i * i * i * i);
     22           }
     23     }
     24 
     25     for (uint64_t i = 0; i < 7072; ++i) {
     26         if (primes[i] != -1) {
     27             for (uint64_t j = 0; j < 369; ++j) {
     28                 if (primes[j] != -1) {
     29                     for (uint64_t k = 0; k < 85; ++k) {
     30                         if (primes[k] != -1) {
     31                             uint64_t candidate = (i * i) + cubes[j] + fourths[k];
     32 
     33                             if (candidate < 50000000) {
     34                                 solutions.insert(candidate);
     35                             }
     36                         }
     37                     }
     38                 }
     39             }
     40         }
     41     }
     42 
     43     return solutions.size();
     44 }