project-euler

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

Euler_5.cpp (1225B)

      1 #include <algorithm>
      2 #include <numeric>
      3 
      4 #include "Euler.h"
      5 
      6 void addNewPrimeFactors(int nextDivisor, std::vector<int> &p_factors, std::vector<int> &primes)
      7 {
      8     std::vector<int> myPrimeFactors(p_factors.size(), 0);
      9     int i = 0;
     10 
     11     while (nextDivisor != 1 && primes[i] <= nextDivisor)
     12     {
     13         if ((primes[i] != -1) && (nextDivisor % primes[i] == 0))
     14         {
     15             nextDivisor /= primes[i];
     16             myPrimeFactors[i] += 1;
     17         }
     18         else
     19             ++i;
     20     }
     21 
     22     for (uint64_t j = 0; j < myPrimeFactors.size(); ++j)
     23         if (p_factors[j] < myPrimeFactors[j])
     24             p_factors[j] = myPrimeFactors[j];
     25 }
     26 
     27 int Euler::DivisibleBy1To20()
     28 {
     29     int ceiling = 20;
     30     std::vector<int> noOfPrimeFactors(ceiling, 0);
     31     std::vector<int> primeFactors;
     32     std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(ceiling);
     33 
     34     for (int i = 2; i <= ceiling; ++i)
     35         addNewPrimeFactors(i, noOfPrimeFactors, primes);
     36 
     37     for (uint64_t i = 0; i < noOfPrimeFactors.size(); ++i)
     38         for (int j = 0; j < noOfPrimeFactors[i]; ++j)
     39             primeFactors.push_back(primes[i]);
     40 
     41     return std::accumulate(primeFactors.begin(), primeFactors.end(), 1, EulerUtility::multiply);
     42 }