fork(1) download
copy 
  1. #include <vector>
  2. #include <tuple>
  3. #include <chrono>
  4. #include <iostream>
  5. #include <inttypes.h>
  6.  
  7. using namespace std;
  8. typedef unsigned int uint;
  9.  
  10. static vector<uint16_t> sieve;
  11. static uint64_t fcnt;
  12.  
  13. void genSieve(uint n, vector<uint16_t> &sieve)
  14. {
  15. 	sieve.clear();
  16. 	uint ye = (n + 1) / 2;
  17. 	sieve.resize(ye, 0);
  18. 	for (uint x = 1; ; x++) {
  19. 		if (sieve[x] != 0)
  20. 			continue;
  21. 		uint p = x + x + 1, yb = (x + x) * (x + 1);
  22. 		if (yb >= ye)
  23. 			break;
  24. 		for (uint y = yb; y < ye; y += p)
  25. 			sieve[y] = x;
  26. 	}
  27. }
  28.  
  29. static void factorize(uint n,  vector<tuple<uint, uint>> &result)
  30.  {
  31. 	result.clear();
  32. 	if (n % 2 == 0) {
  33. 		uint count = 0;
  34. 		do {
  35. 			n /= 2;
  36. 			count++;
  37. 		} while (n % 2 == 0);
  38. 		result.push_back(make_tuple(2, count));
  39. 	}
  40.  
  41. 	for (;;) {
  42. 		uint p = sieve[n / 2];
  43. 		if (p == 0)
  44. 			break;
  45. 		p = p + p + 1;
  46. 		uint count = 0;
  47. 		do {
  48. 			n /= p;
  49. 			count++;
  50. 		} while (n % p == 0);
  51. 		result.push_back(make_tuple(p, count));
  52. 	}
  53. 	if (n > 1)
  54. 		result.push_back(make_tuple(n, 1));
  55. }
  56.  
  57.  
  58. static uint factorial_power(uint m, uint p)
  59. {
  60. 	uint result = 0;
  61. 	while (m >= p) {
  62. 		m /= p;
  63.         result += m;
  64. 	}
  65. 	return result;
  66. }
  67.  
  68. static uint value(uint p, uint k)
  69. {
  70. 	if (k <= p)
  71. 		return k * p;
  72. 	uint res = k - (k - 1) / p;
  73. 	uint resv = res + factorial_power(res, p);	
  74. 	while (resv < k) {
  75. 		fcnt++;
  76. 		res++;
  77. 		resv++;
  78. 		for (uint x = res; x % p == 0; x /= p)
  79. 			resv++;
  80. 	}
  81.  
  82. 	return res * p;
  83. }
  84.  
  85.  
  86. uint s(uint n)
  87. {
  88. 	vector<tuple<uint, uint>> factors;
  89. 	factorize(n, factors);
  90. //return factors.size();
  91.     uint res = 1;
  92.     for (auto v: factors) {
  93.         uint p, k;
  94.         tie(p, k) = v;
  95. #if 1
  96. 		uint r = value(p, k);
  97. 		if (res < r)
  98. 			res = r;
  99. #else
  100.         uint resv = factorial_power(res, p);
  101.         if (resv < k)
  102. 			res = value(p, k);
  103. #endif
  104. 	}
  105. 	return res;
  106. }
  107.  
  108. int main()
  109. {
  110.     auto t1 = chrono::high_resolution_clock::now();
  111.     constexpr int m = 23000000;
  112.     constexpr int n = 24000000;
  113. 	genSieve(n, sieve);
  114.     uint64_t result = 0;
  115.     fcnt = 0;
  116. #if 1
  117.     for (auto i = m; i <= n; ++i)
  118.         result += s(i);
  119. #endif
  120.     auto t2 = chrono::high_resolution_clock::now();
  121. 	cout << result << endl;
  122. 	cout << fcnt << endl;
  123. 	cout << "time: " << chrono::duration_cast<chrono::microseconds>(t2 - t1).count() << "us" << endl;
  124. }
  125.  
  126.  
Success #stdin #stdout 0.28s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2365242607102
17355
time: 291617us
https://ideone.com/bU3bnF
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!