fork(4) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. #include <boost/date_time/local_time/local_time.hpp>
  6.  
  7. typedef unsigned int UInt32;
  8. typedef double Float64;
  9. #define CVector std::vector
  10.  
  11. using namespace std;
  12.  
  13. // Timer class
  14. class CTimer
  15. {
  16. public:
  17.  
  18.     // Starts (or restarts) the timer
  19.     void start() { m_start = now(); }
  20.  
  21.     // Gets the timer elapsed time
  22.     Float64 getElapsedTimeInSeconds()
  23. 	{
  24. 		const auto dur = now() - m_start;
  25. 		return (Float64)dur.total_milliseconds() * 1e-3;
  26. 	}
  27.  
  28. private:
  29.  
  30. 	// Returns the current system time
  31. 	static boost::posix_time::ptime now()
  32. 	{
  33. 		return boost::posix_time::microsec_clock::local_time();
  34. 	}
  35.  
  36. 	boost::posix_time::ptime m_start;
  37.  
  38. };
  39.  
  40. // brute force
  41. UInt32 nextFactorizationOf1(const UInt32 target, const CVector<UInt32>& primes)
  42. {
  43. 	const size_t size = primes.size();
  44. 	UInt32 x = target;
  45. 	while (x < target * 2)
  46. 	{
  47. 		const UInt32 y = x;
  48. 		for(size_t i = 0; i < size && x > 1; ++i)
  49. 		{
  50. 			while(x % primes[i] == 0)
  51. 			{
  52. 				x /= primes[i];
  53. 			}
  54. 		}
  55.  
  56. 		if (x == 1) return y;
  57. 		x = y + 1;
  58. 	}
  59. 	return 0;
  60. }
  61.  
  62. // provided by dasblinkenlight
  63. UInt32 nextFactorizationOf2(const UInt32 target, const CVector<UInt32>& primes)
  64. {
  65. 	set<UInt32> s;
  66. 	s.insert(1);
  67. 	UInt32 best = 2 * target;
  68. 	UInt32 i = 1;
  69. 	while (true)
  70. 	{
  71. 		set<UInt32> next(s.begin(), s.end());
  72. 		for (auto n : s)
  73. 		{
  74. 			for (auto p : primes)
  75. 			{
  76. 				UInt32 x = n * p;
  77. 				if (x < best) next.insert(x);
  78. 			}
  79. 		}
  80.  
  81. 		if (next.size() == s.size()) break;
  82.  
  83. 		//cout << "Generation " << i++ << ", best = " << best << endl;
  84. 		for (auto n : next)
  85. 		{
  86. 			if (n >= target && n < best) best = n;
  87. 		}
  88. 		s = next;
  89. 	}
  90. 	return best;
  91. }
  92.  
  93. // provided by anatolyg
  94. UInt32 nextFactorizationOf3(const UInt32 target, const CVector<UInt32>& primes, UInt32 product=1)
  95. {
  96.     if (product >= target) return product;
  97.  
  98. 	UInt32 ret = target * 2;
  99.     for (auto prime : primes)
  100. 	{
  101.         ret = min(ret, nextFactorizationOf3(target, primes, product * prime));
  102. 	}
  103. 	return ret;
  104. }
  105.  
  106. // provided by Ivan Gritsenko
  107. UInt32 nextFactorizationOf4(const UInt32 target, const CVector<UInt32>& primes)
  108. {
  109. 	// initialize bestCandidate as a power of some prime greater than num
  110. 	UInt32 bestCandidate = 1;
  111. 	while (bestCandidate < target) bestCandidate *= primes[0];
  112.  
  113. 	set<UInt32> s;
  114. 	s.insert(1);
  115. 	while (!s.empty())
  116. 	{
  117. 		UInt32 current = *s.begin();
  118. 		s.erase(s.begin());
  119.  
  120. 		for (auto p : primes)
  121. 		{
  122. 			UInt32 newCandidate = current * p;
  123. 			if (newCandidate < target)
  124. 			{
  125. 				// new lower candidates should be stored.
  126. 				if (s.find(newCandidate) == s.end()) s.insert(newCandidate);
  127. 			}
  128. 			else
  129. 			{
  130. 				if (newCandidate < bestCandidate) bestCandidate = newCandidate;
  131. 				break; // further iterations will generate only larger numbers
  132. 			}
  133. 		}
  134. 	}
  135. 	return bestCandidate;
  136. }
  137.  
  138. // utility function to help "fool" the compiler
  139. bool validate(const CVector<UInt32>& results)
  140. {
  141. 	const size_t size = results.size();
  142. 	for (size_t i = 1; i < size; ++i)
  143. 	{
  144. 		if (results[i] != results[0]) return false;
  145. 	}
  146. 	return true;
  147. }
  148.  
  149. // Note: The results do not need to be stored in a vector or validated,
  150. //       that is simply done to help "fool" the compiler so that certain
  151. //       optimizations do not occur that would affect the timing results
  152. int main() {
  153. 	CTimer timer;
  154. 	const CVector<UInt32> primes = { 2, 3, 5, 7 };
  155. 	const CVector<UInt32> tests = { 5917, 8192, 262145 };
  156. 	const size_t iterations = 50;
  157. 	CVector<UInt32> results(iterations);
  158.  
  159. 	for (const auto num : tests)
  160. 	{
  161. 		timer.start();
  162. 		for (size_t i = 0; i < iterations; ++i) results[i] = nextFactorizationOf1(num, primes);
  163. 		const Float64 elapsed1 = timer.getElapsedTimeInSeconds();
  164. 		const UInt32 result1 = results[0];
  165. 		if (!validate(results)) cout << endl << "Failure!";
  166.  
  167. 		timer.start();
  168. 		for (size_t i = 0; i < iterations; ++i) results[i] = nextFactorizationOf2(num, primes);
  169. 		const Float64 elapsed2 = timer.getElapsedTimeInSeconds();
  170. 		const UInt32 result2 = results[0];
  171. 		if (!validate(results)) cout << endl << "Failure!";
  172.  
  173. 		timer.start();
  174. 		for (size_t i = 0; i < iterations; ++i) results[i] = nextFactorizationOf3(num, primes);
  175. 		const Float64 elapsed3 = timer.getElapsedTimeInSeconds();
  176. 		const UInt32 result3 = results[0];
  177. 		if (!validate(results)) cout << endl << "Failure!";
  178.  
  179. 		timer.start();
  180. 		for (size_t i = 0; i < iterations; ++i) results[i] = nextFactorizationOf4(num, primes);
  181. 		const Float64 elapsed4 = timer.getElapsedTimeInSeconds();
  182. 		const UInt32 result4 = results[0];
  183. 		if (!validate(results)) cout << endl << "Failure!";
  184.  
  185. 		cout << endl << "Results for " << num << ":"
  186. 			 << endl << result1 << " in " << elapsed1 << " s."
  187. 			 << endl << result2 << " in " << elapsed2 << " s."
  188. 			 << endl << result3 << " in " << elapsed3 << " s."
  189. 			 << endl << result4 << " in " << elapsed4 << " s."
  190. 			 << endl;
  191. 	}
  192. 	cout << "Press [ENTER] to exit..." << flush;
  193. 	cin.ignore(1);
  194.  
  195. 	return 0;
  196. }
Success #stdin #stdout 2.53s 3448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Results for 5917:
6000 in 0 s.
6000 in 0.045 s.
6000 in 0.027 s.
6000 in 0.004 s.

Results for 8192:
8192 in 0 s.
8192 in 0.056 s.
8192 in 0.04 s.
8192 in 0.004 s.

Results for 262145:
262440 in 0.002 s.
262440 in 0.227 s.
262440 in 2.113 s.
262440 in 0.015 s.
Press [ENTER] to exit...
https://ideone.com/HAgDsF
language:
C++14 (gcc 8.3)
created:
9 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!