project-euler

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

Euler_29.cpp (1715B)

      1 #include <unordered_set>
      2 
      3 #include "Euler.h"
      4 
      5 std::vector<int> getPowers(int ceiling)
      6 {
      7     std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(ceiling);
      8     std::vector<int> powers(ceiling + 1, 0);
      9 
     10     for (int j = 0; j <= ceiling; ++j)
     11     {
     12         std::vector<int> p_factors;
     13         int target = j;
     14         int i = 0;
     15 
     16         while (target > 1)
     17         {
     18             if (target % primes[i] == 0)
     19             {
     20                 target /= primes[i];
     21                 p_factors.push_back(primes[i]);
     22             }
     23             else
     24                 ++i;
     25         }
     26 
     27         if (p_factors.size() > 1)
     28         {
     29             std::unordered_set<int> unique_p_factors;
     30 
     31             for (int p : p_factors)
     32                 unique_p_factors.insert(p);
     33 
     34             if (unique_p_factors.size() == 1)
     35                 powers[j] = p_factors.size();
     36             else if (EulerUtility::isPerfectSquare(j))
     37                 powers[j] = 2;
     38         }
     39     }
     40 
     41     return powers;
     42 }
     43 
     44 int Euler::DistinctPowers()
     45 {
     46     int ceiling = 100;
     47     std::vector<int> powers = getPowers(ceiling);
     48 
     49     int sum = 0;
     50 
     51     for (int i = 2; i <= ceiling; ++i)
     52     {
     53         if (powers[i] == 0)
     54             sum += ceiling - 1;
     55         else
     56         {
     57             for (int j = 2; j <= ceiling; ++j)
     58             {
     59                 bool unique = true;
     60 
     61                 for (int k = 1; k < powers[i]; ++k)
     62                 {
     63                     if (((powers[i] * j) % k == 0) && ((powers[i] * j) / k <= ceiling))
     64                     {
     65                         unique = false;
     66                         break;
     67                     }
     68                 }
     69 
     70                 if (unique)
     71                     ++sum;
     72             }
     73         }
     74     }
     75 
     76     return sum;
     77 }