fork(1) download 
  1. /*	(c) WhiZTiM __ionogu(<_at__)>acm.org
  2. 	Cheat sheats.... :-)
  3. 	*/
  4.  
  5. #include <type_traits>
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <string>
  9. #include <chrono>
  10. #include <cmath>
  11.  
  12. namespace detail {
  13. 	template<typename M, typename N>
  14. 	constexpr typename std::common_type<M, N>::type lcm_Impl(M m, N n, M increment){
  15. 		return m % n == 0 ? m : lcm_Impl(m + increment, n, increment);
  16. 	}
  17. }
  18.  
  19. template<typename Func, typename... Args>
  20. void timeit(Func func, Args&&... args){
  21. 	auto start = std::chrono::high_resolution_clock::now();
  22. 	func(std::forward<Args&&>(args)...);
  23. 	auto stop = std::chrono::high_resolution_clock::now();
  24. 	std::cout.precision(8);
  25. 	std::cout << 
  26. 		"Took: " << std::chrono::duration<double, std::ratio<1,1>>(stop - start).count()
  27. 		<< " seconds\n";
  28. }
  29.  
  30.  
  31.  
  32. /*! Returns the Greatest Common Divisor of two numbers
  33.     Precondition: m > n; */
  34. template<typename M, typename N>
  35. constexpr typename std::common_type<M, N>::type gcd(M m, N n){
  36. 	return n == 0 ? m : gcd(n, m%n);
  37. }
  38.  
  39. /*! Returns the Lowest Common Multiple of two numbers
  40.     Precondition: m > n; */
  41. template<typename M, typename N>
  42. constexpr auto lcm(M m, N n){
  43. 	return detail::lcm_Impl(m, n, m);
  44. }
  45.  
  46. /*! Returns all the factors of 'number'
  47.     Precondition: number > 0; */
  48. template<typename T>
  49. std::vector<T> simple_factors(T number){
  50. 	std::vector<T> rtn;
  51. 	T bound = std::sqrt(number);
  52. 	for(T i=1; i < bound; i++)
  53. 		if(number % i == 0){
  54. 			rtn.emplace_back(i);
  55. 			rtn.emplace_back(number / i);
  56. 		}
  57. 	std::sort(rtn.begin(), rtn.end());
  58. 	return rtn;
  59. }
  60.  
  61. /*! Simple but Fast Fibonacci solver; (Memorization)
  62.     Postcondition: memory consumed is the maximum index computed;
  63. 	Example: 
  64. 	* Fibonacci fb; auto m = fb.compute(50);
  65. 	* int fib = Fibonacci().compute(21);
  66. 	* auto fib = Fibonacci().compute(100);
  67. 	*/
  68. class Fibonacci {
  69. public: //... once you, the client alter memory, there's no guarantee of correctness again
  70. 	std::vector<std::uint64_t> memory = {0, 1, 1};
  71. public:
  72. 	std::uint64_t compute(std::size_t index){
  73. 		if(index < memory.size())
  74. 			return memory[index];
  75. 		auto c1 = compute(index - 1);
  76. 		auto c2 = compute(index - 2);
  77. 		auto c3 = c1 + c2;
  78. 		memory.emplace_back(c3);
  79. 		return c3;
  80. 	}
  81. };
  82.  
  83.  
  84.  
  85. struct DumbCallback{
  86. 	template<typename T>
  87. 	constexpr bool operator () (T) { return true; }
  88. };
  89.  
  90.  
  91.  
  92. /*! Fast Prime Number Generator using Sieve of Eratosthenes;
  93.     Example:
  94.     *  auto primes = EratosthenesSieve<>().sieve();
  95.     *  auto primes = EratosthenesSieve<10'000'000>().sieve();
  96.     *  std::vector<std::size_t> primes = EratosthenesSieve<>().sieve();
  97.     *  auto primes = EratosthenesSieve<10'000'000, std::int64_t>().sieve();
  98.     *  etc.... */
  99. template<std::size_t max = 1'000'000,
  100. 			typename Type = typename std::conditional<
  101. 					(max <= std::numeric_limits<std::size_t>::max()), std::size_t, unsigned long
  102. 					>::type
  103.     >
  104. class EratosthenesSieve{
  105. public:
  106.     static_assert(max > 2, "Sieve size must be greater than 2");
  107.  
  108. 	using value_type = Type;
  109.  
  110. 	template<typename Callback = DumbCallback>
  111.     inline std::vector<Type> sieve(Callback callback = DumbCallback()) const {
  112.  
  113. 		std::vector<Type> rtn;
  114. 		bool flag[max];
  115. 		//! std::fill will use memset
  116. 		std::fill(std::begin(flag) + 2, std::end(flag), false);
  117. 		std::fill(std::begin(flag), std::begin(flag) + 2, true);
  118. 		for(std::size_t index = 2; index < max; index++)
  119. 			if(not flag[index])
  120. 			for(std::size_t i = 2*index; i < max; i += index)
  121. 				flag[i] = true;
  122.  
  123. 		for(std::size_t idx = 0; idx < max; idx++)
  124. 			if(not flag[idx] and callback(idx)){
  125. 				rtn.emplace_back(idx);
  126. 			}
  127.  
  128. 		return rtn;
  129.     }
  130. };
  131.  
  132.  
  133. int main(){
  134. 	return 0;
  135. }
Success #stdin #stdout 0s 3092KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/NqHgtM
This is just a rough sample of my algorithm headers...
Will be updated as the need arises
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!