project-euler

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

Euler_12.cpp (1162B)

      1 #include "Euler.h"
      2 
      3 int getNumberOfDivisorsFromPrimeFactors(llui target, std::vector<int> &primes)
      4 {
      5     std::vector<int> noOfEachPrimeFactor;
      6 
      7     int divisors = 1;
      8     int i = 0;
      9 
     10     bool first = true;
     11 
     12     while (target != 1)
     13     {
     14         if (target % primes[i] == 0)
     15         {
     16             target /= primes[i];
     17 
     18             if (first)
     19             {
     20                 first = false;
     21                 noOfEachPrimeFactor.push_back(1);
     22             }
     23             else
     24                 noOfEachPrimeFactor[noOfEachPrimeFactor.size() - 1] += 1;
     25         }
     26         else
     27         {
     28             first = true;
     29             ++i;
     30         }
     31     }
     32 
     33     if (!noOfEachPrimeFactor.empty())
     34     {
     35         for (unsigned i = 0; i < noOfEachPrimeFactor.size(); ++i)
     36         {
     37             divisors *= (noOfEachPrimeFactor[i] + 1);
     38         }
     39     }
     40 
     41     return divisors;
     42 }
     43 
     44 llui Euler::TriangleNoWithGreaterThan500Divisors()
     45 {
     46     llui currentTriangle = 1;
     47 
     48     std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(100000);
     49 
     50     for (int i = 2; getNumberOfDivisorsFromPrimeFactors(currentTriangle, primes) <= 500; ++i)
     51         currentTriangle += i;
     52 
     53     return currentTriangle;
     54 }