project-euler

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

Euler_47.cpp (815B)

      1 #include <unordered_set>
      2 
      3 #include "Euler.h"
      4 
      5 std::unordered_set<int> distinctPrimeFactors(llui target, std::vector<int> &primes)
      6 {
      7     std::unordered_set<int> distinctPrimeFactors;
      8 
      9     int i = 0;
     10 
     11     while (target != 1)
     12     {
     13         if (target % primes[i] == 0)
     14         {
     15             target /= primes[i];
     16             distinctPrimeFactors.insert(primes[i]);
     17         }
     18         else
     19             ++i;
     20     }
     21 
     22     return distinctPrimeFactors;
     23 }
     24 
     25 int Euler::DistinctPrimeFactors()
     26 {
     27     int consecutive = 0;
     28     std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(1000000);
     29 
     30         for (int i = 647; ; ++i)
     31         {
     32             consecutive = (distinctPrimeFactors(i, primes).size() == 4) ? consecutive + 1 : 0;
     33 
     34             if (consecutive == 4)
     35                 return i - 3;
     36         }
     37 
     38         return 0;
     39 }