project-euler

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

Euler_60.cpp (1856B)

      1 #include <algorithm>
      2 #include <unordered_set>
      3 
      4 #include "Euler.h"
      5 
      6 int Euler::PrimePairSets()
      7 {
      8     std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(100000);
      9 
     10     std::vector<std::vector<int>> concatPrimes(10000, std::vector<int>());
     11 
     12     for (int i = 0; i < 10000; ++i)
     13     {
     14         if (EulerUtility::isPrime(i, 5))
     15         {
     16             for (int p : primes)
     17             {
     18                 if (p < i)
     19                 {
     20                     std::vector<int> concat(1, i);
     21                     concat.push_back(p);
     22 
     23                     int c = EulerUtility::digitsToInteger(concat);
     24 
     25                     if (EulerUtility::isPrime(c, 5))
     26                     {
     27                         std::swap(concat[0], concat[1]);
     28                         c = EulerUtility::digitsToInteger(concat);
     29 
     30                         if (EulerUtility::isPrime(c, 5))
     31                         {
     32                             concatPrimes[i].push_back(p);
     33                             concatPrimes[p].push_back(i);
     34                         }
     35                     }
     36                 }
     37                 else
     38                     break;
     39             }
     40         }
     41     }
     42 
     43     for (int i = 0; i < 10000; ++i)
     44     {
     45          for (int j : concatPrimes[i])
     46         {
     47             std::vector<int> intersection_a = EulerUtility::intersect(concatPrimes[i], concatPrimes[j]);
     48 
     49             for (int k : intersection_a)
     50             {
     51                 std::vector<int> intersection_b = EulerUtility::intersect(intersection_a, concatPrimes[k]);
     52 
     53                 for (int l : intersection_b)
     54                 {
     55                     std::vector<int> intersection_c = EulerUtility::intersect(intersection_b, concatPrimes[l]);
     56 
     57                     if (intersection_c.size() > 0)
     58                         return i + j + k + l + intersection_c[0];
     59                 }
     60             }
     61         }
     62     }
     63 
     64     return 0;
     65 }