fork download
copy 
  1. #include <utility>
  2. #include <vector>
  3.  
  4. std::vector< std::pair<int, int> > factor_table;
  5. void fill_sieve( int n )
  6. {
  7. 	factor_table.resize(n+1);
  8. 	for( int i = 1; i <= n; ++i )
  9. 		factor_table[i] = std::pair<int, int>(i, 1);
  10. 	for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
  11. 		if (factor_table[j].second == 1) {
  12. 			int i = j;
  13. 			int ij = j2;
  14. 			while (ij <= n) {
  15. 				factor_table[ij] = std::pair<int, int>(j, i);
  16. 				++i;
  17. 				ij += j;
  18. 			}
  19. 		}
  20. 	}
  21. }
  22.  
  23. std::vector<unsigned> powers;
  24.  
  25. template<int dir>
  26. void factor( int num )
  27. {
  28. 	while (num != 1) {
  29. 		powers[factor_table[num].first] += dir;
  30. 		num = factor_table[num].second;
  31. 	}
  32. }
  33.  
  34. template<unsigned N>
  35. void calc_combinations(unsigned (&bin_sizes)[N])
  36. {
  37. 	using std::swap;
  38.  
  39. 	powers.resize(0);
  40. 	if (N < 2) return;
  41.  
  42. 	unsigned& largest = bin_sizes[0];
  43. 	size_t sum = largest;
  44. 	for( int bin = 1; bin < N; ++bin ) {
  45. 		unsigned& this_bin = bin_sizes[bin];
  46. 		sum += this_bin;
  47. 		if (this_bin > largest) swap(this_bin, largest);
  48. 	}
  49. 	fill_sieve(sum);
  50.  
  51. 	powers.resize(sum+1);
  52. 	for( unsigned i = largest + 1; i <= sum; ++i ) factor<+1>(i);
  53. 	for( unsigned bin = 1; bin < N; ++bin )
  54. 		for( unsigned j = 2; j <= bin_sizes[bin]; ++j ) factor<-1>(j);
  55. }
  56.  
  57. #include <iostream>
  58. #include <cmath>
  59. int main(void)
  60. {
  61. 	unsigned bin_sizes[] = { 5, 15 };
  62. 	calc_combinations(bin_sizes);
  63. 	char* sep = "";
  64. 	for( unsigned i = 0; i < powers.size(); ++i ) {
  65. 		if (powers[i]) {
  66. 			std::cout << sep << i;
  67. 			sep = " * ";
  68. 			if (powers[i] > 1)
  69. 				std::cout << "**" << powers[i];
  70. 		}
  71. 	}
  72. 	std::cout << "\n\n";
  73. }
  74.  
Success #stdin #stdout 0.02s 2816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2**4 * 3 * 17 * 19
https://ideone.com/5L9LU
language:
C++ (gcc 8.3)
created:
11 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!