fork download
copy 
  1. /**
  2.  * Problem 12
  3.  * ----------
  4.  * The sequence of triangle numbers is generated by adding the natural numbers.
  5.  * So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The
  6.  * first ten terms would be:
  7.  *   1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
  8.  *
  9.  * Let us list the factors of the first seven triangle numbers:
  10.  *   1: 1
  11.  *   3: 1,3
  12.  *   6: 1,2,3,6
  13.  *   10: 1,2,5,10
  14.  *   15: 1,3,5,15
  15.  *   21: 1,3,7,21
  16.  *   28: 1,2,4,7,14,28
  17.  *
  18.  * We can see that 28 is the first triangle number to have over five divisors.
  19.  *
  20.  * What is the value of the first triangle number to have over five hundred
  21.  * divisors?
  22.  */
  23.  
  24.  
  25. #include <algorithm>
  26. #include <chrono>
  27. #include <cmath>
  28. #include <iostream>
  29. #include <map>
  30. #include <vector>
  31. #include <stdint.h>
  32.  
  33.  
  34.  
  35. typedef std::map<uint64_t, uint64_t> Map;
  36. Map get_prime_factors(uint64_t n);
  37.  
  38.  
  39. template<typename T>
  40. std::ostream& operator<<(std::ostream & os, const std::vector<T> & vec)
  41. {
  42.     os << "{ ";
  43.     for (const auto & v : vec)
  44.     {
  45.         os << v << " ";
  46.     }
  47.     return os << "}";
  48. }
  49.  
  50. template<typename T>
  51. std::ostream& operator<<(std::ostream & os, const std::map<T, T> & vec)
  52. {
  53.     uint64_t c = 0;
  54.     for (const auto & p : vec)
  55.     {
  56.         if (c++)
  57.         {
  58.             os << '*';
  59.         }
  60.         for (uint64_t i = 0; i < p.second; ++i)
  61.         {
  62.             if (i != 0)
  63.             {
  64.                 os << '*';
  65.             }
  66.             os << p.first;
  67.         }
  68.     }
  69.     return os;
  70. }
  71.  
  72.  
  73. bool is_prime(uint64_t n, const std::vector<uint64_t> & preceding)
  74. {
  75.     // precondition: "preceding" contains all primes < sqrt(n)
  76.  
  77.     for (auto p : preceding)
  78.     {
  79.         if ((p * p) > n)
  80.         {
  81.             return true;
  82.         }
  83.  
  84.         if (n % p == 0)
  85.         {
  86.             return false;
  87.         }
  88.     }
  89.     return true;
  90. }
  91.  
  92.  
  93. uint64_t next_prime(std::vector<uint64_t> & preceding)
  94. {
  95.     if (preceding.empty())
  96.     {
  97.         preceding.push_back(2);
  98.         return preceding.back();
  99.     }
  100.  
  101.     if (preceding.back() == 2)
  102.     {
  103.         preceding.push_back(3);
  104.         return preceding.back();
  105.     }
  106.  
  107.     for (uint64_t n = preceding.back() + 2; ; n += 2)
  108.     {
  109.         if (is_prime(n, preceding))
  110.         {
  111.             preceding.push_back(n);
  112.             return preceding.back();
  113.         }
  114.     }
  115. }
  116.  
  117.  
  118. uint64_t num_divisors(uint64_t n)
  119. {
  120.     uint64_t result = 1;
  121.     for (auto pair : get_prime_factors(n))
  122.     {
  123.         result *= (pair.second + 1);
  124.     }
  125.     return result;
  126. }
  127.  
  128.  
  129. uint64_t triangle(uint64_t n)
  130. {
  131.     return n % 2 == 0 ? (n/2) * (n+1) : ((n+1)/2) * n;
  132. }
  133.  
  134.  
  135.  
  136. Map operator+(Map lhs, const Map & rhs)
  137. {
  138.     for (auto p : rhs)
  139.     {
  140.         lhs[p.first] += p.second;
  141.     }
  142.     return lhs;
  143. }
  144.  
  145.  
  146. Map get_prime_factors(uint64_t n)
  147. {
  148.     std::map<uint64_t, uint64_t> result;
  149.     static std::vector<uint64_t> pre = []{
  150.         std::vector<uint64_t> result;
  151.         for (int i = 0; i < 15000; ++i)
  152.         {
  153.             next_prime(result);
  154.         }
  155.         return result;
  156.     }();
  157.  
  158.     if (n >= pre.size()) throw "n exceeds precalculated";
  159.  
  160.     for (uint64_t i = 0; i < pre.size(); ++i)
  161.     {
  162.         auto p = pre[i];
  163.         while (n % p == 0)
  164.         {
  165.             result[p]++;
  166.             n /= p;
  167.         }
  168.         if (p > n)
  169.         {
  170.             return result;
  171.         }
  172.     }
  173.     return result;
  174. }
  175.  
  176.  
  177. Map get_prime_factors_of_tr(uint64_t n)
  178. {
  179.     if (n%2 ==0)
  180.     {
  181.         return get_prime_factors(n/2) + get_prime_factors(n + 1);
  182.     }
  183.     else
  184.     {
  185.         return get_prime_factors(n) + get_prime_factors((n + 1)/2);
  186.     }
  187. }
  188.  
  189.  
  190. uint64_t get_divisors_count_of_tr(uint64_t n)
  191. {
  192.     uint64_t result = 1;
  193.     for (auto pair : get_prime_factors_of_tr(n))
  194.     {
  195.         result *= pair.second + 1;
  196.     }
  197.     return result;
  198. }
  199.  
  200.  
  201. class Stopwatch
  202. {
  203. public:
  204.     typedef std::chrono::high_resolution_clock Clock;
  205.  
  206.     //! Constructor starts the stopwatch
  207.     Stopwatch() : mStart(Clock::now())
  208.     {
  209.     }
  210.  
  211.     //! Returns elapsed number of seconds in decimal form.
  212.     double elapsed()
  213.     {
  214.         return 1.0 * (Clock::now() - mStart).count() / Clock::period::den;
  215.     }
  216.  
  217.     Clock::time_point mStart;
  218. };
  219.  
  220.  
  221. int main()
  222. {
  223.     Stopwatch sw;
  224.     for (uint64_t i = 2; ; ++i)
  225.     {
  226.         auto div = get_divisors_count_of_tr(i);
  227.         if (div > 500)
  228.         {
  229.             std::cout << triangle(i) << std::endl;
  230.             break;
  231.         }
  232.     }
  233.     std::cout << (1000 * sw.elapsed()) << "ms" << std::endl;
  234. }
  235.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_RealType>&)':
prog.cpp:43:25: error: expected initializer before ':' token
prog.cpp:47:5: error: expected primary-expression before 'return'
prog.cpp:47:5: error: expected ';' before 'return'
prog.cpp:47:5: error: expected primary-expression before 'return'
prog.cpp:47:5: error: expected ')' before 'return'
prog.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::map<T, T>&)':
prog.cpp:54:25: error: expected initializer before ':' token
prog.cpp:234:1: error: expected primary-expression at end of input
prog.cpp:234:1: error: expected ';' at end of input
prog.cpp:234:1: error: expected primary-expression at end of input
prog.cpp:234:1: error: expected ')' at end of input
prog.cpp:234:1: error: expected statement at end of input
prog.cpp:234:1: error: expected '}' at end of input
stdout
copy 
Standard output is empty
https://ideone.com/NNo4aG
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!