project-euler

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

Euler_51.cpp (1584B)

      1 #include <algorithm>
      2 #include "Euler.h"
      3 
      4 struct pair
      5 {
      6     int prime;
      7     int digit;
      8 };
      9 
     10 int Euler::PrimeDigitReplacements()
     11 {
     12     std::vector<int> primes = EulerUtility::getPrimesUnderCeilingIndexed(1000000);
     13     std::vector<pair> candidates;
     14 
     15     for (int prime : primes)
     16     {
     17         if (prime != -1)
     18         {
     19             std::vector<int> digits = EulerUtility::intToDigits(prime);
     20 
     21             int repeatedDigits[3] = {0, 0, 0};
     22 
     23             for (uint64_t i = 0; i < digits.size() - 1; ++i)
     24                 if (digits[i] <= 2)
     25                     ++repeatedDigits[digits[i]];
     26 
     27             for (int i = 0; i < 3; ++i)
     28                 if (repeatedDigits[i] == 3)
     29                 {
     30                     pair p;
     31                     p.prime = prime;
     32                     p.digit = i;
     33                     candidates.push_back(p);
     34                 }
     35         }
     36     }
     37 
     38     for (pair p : candidates)
     39     {
     40         std::vector<int> digits = EulerUtility::intToDigits(p.prime);
     41         std::vector<int> indices;
     42         int sizeOfFamily = 1;
     43 
     44         for (uint64_t i = 0; i < digits.size() - 1; ++i)
     45             if (digits[i] == p.digit)
     46                 indices.push_back(i);
     47 
     48         for (int i = 0; i < 10; ++i)
     49         {
     50             if ((i != p.digit) && (i != 0 || indices[0] != 0))
     51             {
     52                 for (int idx : indices)
     53                     digits[idx] = i;
     54 
     55                 if (primes[EulerUtility::digitsToInteger(digits)] > 0)
     56                     ++sizeOfFamily;
     57             }
     58         }
     59 
     60         if (sizeOfFamily >= 8)
     61             return p.prime;
     62     }
     63 
     64     return 0;
     65 }