fork(3) download
copy 
  1. #include <cmath>
  2. #include <vector>
  3. #include <iostream>
  4. #include <tuple>
  5. #include <chrono>
  6.  
  7. using namespace std;
  8. typedef unsigned int uint;
  9.  
  10. vector<int> primes({ 2, 3, 5, 7, 11, 13 });
  11.  
  12. void genPrimes(int max) {
  13.     for (int n = 15; n <= max; n += 2) {
  14.         auto it = primes.begin() + 1;
  15.         for (;;) {
  16.             if (it == primes.end()) {
  17.                 primes.push_back(n);
  18.                 break;
  19.             }
  20.             if (n % *it == 0) break;
  21.             ++it;
  22.         }
  23.     }
  24. }
  25.  
  26.  
  27. static vector<tuple<uint, uint>> factorize(uint n) {
  28.     vector<tuple<uint, uint>> result;
  29.     for (auto p : primes) {
  30. 		uint q = n / p, r = n % p;
  31. 		if (q < p)
  32. 			break;
  33. 		if (r != 0)
  34. 			continue;
  35. 		uint count = 1;
  36. 		while (q % p == 0) {
  37. 			count++;
  38. 			q /= p;
  39. 		}
  40. 		n = q;
  41. 		result.push_back(make_tuple(p, count));
  42. 	}
  43. 	if (n > 1)
  44. 		result.push_back(make_tuple(n, 1));
  45. 	return result;
  46. }
  47.  
  48. static uint factorial_power(uint m, uint p)
  49. {
  50. 	uint result = 0;
  51. 	while (m >= p) {
  52. 		m /= p;
  53.         result += m;
  54. 	}
  55. 	return result;
  56. }
  57.  
  58.  
  59. uint s(uint n)
  60. {
  61.     auto factors = factorize(n);
  62.     uint lb = 1;
  63.     for (auto v: factors)
  64.     {
  65.         uint p;
  66.         uint count;
  67.         tie(p, count) = v;
  68.         int lb_value = factorial_power(lb, p);
  69.         if (lb_value >= count) continue;
  70.         int ub = p * count;
  71.         if (count < p)
  72.         {
  73.             lb = ub;
  74.             continue;
  75.         }
  76.         while (lb < ub)
  77.         {
  78.             int median = lb + (ub - lb) / 2;
  79.             int m_value = factorial_power(median, p);
  80.             if (m_value < count)
  81.             {
  82.                 lb = median + 1;
  83.             }
  84.             else
  85.             {
  86.                 ub = median;
  87.             }
  88.         }
  89.     }
  90.     return lb;
  91. }
  92.  
  93. int main()
  94. {
  95.     auto t1 = chrono::high_resolution_clock::now();
  96.     constexpr int m = 2300000;
  97.     constexpr int n = 2400000;
  98.     genPrimes(static_cast<int>(sqrt(n)));
  99.     int64_t result = 0;
  100.     for (auto i = m; i <= n; ++i)
  101.         result += s(i);
  102.  
  103.     auto t2 = chrono::high_resolution_clock::now();
  104. 	cout << result << endl;
  105. 	cout << "time: " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << "ms" << endl;
  106. }
  107.  
  108.  
Success #stdin #stdout 0.04s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
27566064194
time: 38ms
https://ideone.com/EYytGR
language:
C++14 (gcc 8.3)
created:
7 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!