fork(6) 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. void calc_catalan(unsigned N)
  35. {
  36.     powers.resize(N+1);
  37.     for( unsigned k = 2; k <= N; ++k ) {
  38.          factor<+1>(k+N);
  39.          factor<-1>(k);
  40.     }
  41. }
  42.  
  43. #include <iostream>
  44. #include <cmath>
  45. int main(void)
  46. {
  47.     fill_sieve(20000);
  48.     unsigned N = 9913;
  49.     calc_catalan(N);
  50.     char* sep = "";
  51.     for( unsigned i = 0; i < powers.size(); ++i ) {
  52.     	if (powers[i]) {
  53.     	    std::cout << sep << i;
  54.     	    sep = " * ";
  55.     	    if (powers[i] > 1)
  56.     	        std::cout << "**" << powers[i];
  57.     	}
  58.     }
  59.     std::cout << "\n\n";
  60. }
Success #stdin #stdout 0.01s 2816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2**7 * 3**5 * 5**4 * 7**2 * 11**2 * 13**3 * 19 * 23**2 * 29**2 * 31 * 37 * 41**2 * 43 * 47 * 53 * 59 * 61**2 * 67 * 71**2 * 73**2 * 79 * 101 * 103 * 107**2 * 109**2 * 113**2 * 127 * 131**2 * 137 * 139 * 149 * 151 * 163 * 181 * 191 * 199 * 211 * 227 * 233 * 257 * 263 * 269 * 271 * 277 * 293 * 311 * 313 * 331 * 347 * 359 * 373 * 383 * 397 * 401 * 419 * 421 * 433 * 439 * 457 * 461 * 479 * 499 * 503 * 523 * 557 * 563 * 587 * 593 * 599 * 631 * 661 * 673 * 677 * 683 * 709 * 719 * 727 * 733 * 769 * 773 * 787 * 827 * 829 * 839 * 853 * 857 * 859 * 907 * 911 * 919 * 929 * 937 * 941 * 997 * 1009 * 1013 * 1019 * 1021 * 1031 * 1033 * 1039 * 1103 * 1109 * 1117 * 1123 * 1129 * 1151 * 1153 * 1163 * 1249 * 1259 * 1277 * 1279 * 1283 * 1289 * 1291 * 1297 * 1301 * 1303 * 1307 * 1319 * 1321 * 1423 * 1427 * 1429 * 1433 * 1439 * 1447 * 1451 * 1453 * 1459 * 1471 * 1481 * 1483 * 1487 * 1489 * 1493 * 1499 * 1511 * 1523 * 1657 * 1663 * 1667 * 1669 * 1693 * 1697 * 1699 * 1709 * 1721 * 1723 * 1733 * 1741 * 1747 * 1753 * 1759 * 1777 * 1783 * 1787 * 1789 * 1801 * 1987 * 1993 * 1997 * 1999 * 2003 * 2011 * 2017 * 2027 * 2029 * 2039 * 2053 * 2063 * 2069 * 2081 * 2083 * 2087 * 2089 * 2099 * 2111 * 2113 * 2129 * 2131 * 2137 * 2141 * 2143 * 2153 * 2161 * 2179 * 2503 * 2521 * 2531 * 2539 * 2543 * 2549 * 2551 * 2557 * 2579 * 2591 * 2593 * 2609 * 2617 * 2621 * 2633 * 2647 * 2657 * 2659 * 2663 * 2671 * 2677 * 2683 * 2687 * 2689 * 2693 * 2699 * 2707 * 2711 * 2713 * 2719 * 2729 * 2731 * 2741 * 2749 * 2753 * 2767 * 2777 * 2789 * 2791 * 2797 * 2801 * 2803 * 2819 * 3307 * 3313 * 3319 * 3323 * 3329 * 3331 * 3343 * 3347 * 3359 * 3361 * 3371 * 3373 * 3389 * 3391 * 3407 * 3413 * 3433 * 3449 * 3457 * 3461 * 3463 * 3467 * 3469 * 3491 * 3499 * 3511 * 3517 * 3527 * 3529 * 3533 * 3539 * 3541 * 3547 * 3557 * 3559 * 3571 * 3581 * 3583 * 3593 * 3607 * 3613 * 3617 * 3623 * 3631 * 3637 * 3643 * 3659 * 3671 * 3673 * 3677 * 3691 * 3697 * 3701 * 3709 * 3719 * 3727 * 3733 * 3739 * 3761 * 3767 * 3769 * 3779 * 3793 * 3797 * 3803 * 3821 * 3823 * 3833 * 3847 * 3851 * 3853 * 3863 * 3877 * 3881 * 3889 * 3907 * 3911 * 3917 * 3919 * 3923 * 3929 * 3931 * 3943 * 3947 * 4967 * 4969 * 4973 * 4987 * 4993 * 4999 * 5003 * 5009 * 5011 * 5021 * 5023 * 5039 * 5051 * 5059 * 5077 * 5081 * 5087 * 5099 * 5101 * 5107 * 5113 * 5119 * 5147 * 5153 * 5167 * 5171 * 5179 * 5189 * 5197 * 5209 * 5227 * 5231 * 5233 * 5237 * 5261 * 5273 * 5279 * 5281 * 5297 * 5303 * 5309 * 5323 * 5333 * 5347 * 5351 * 5381 * 5387 * 5393 * 5399 * 5407 * 5413 * 5417 * 5419 * 5431 * 5437 * 5441 * 5443 * 5449 * 5471 * 5477 * 5479 * 5483 * 5501 * 5503 * 5507 * 5519 * 5521 * 5527 * 5531 * 5557 * 5563 * 5569 * 5573 * 5581 * 5591 * 5623 * 5639 * 5641 * 5647 * 5651 * 5653 * 5657 * 5659 * 5669 * 5683 * 5689 * 5693 * 5701 * 5711 * 5717 * 5737 * 5741 * 5743 * 5749 * 5779 * 5783 * 5791 * 5801 * 5807 * 5813 * 5821 * 5827 * 5839 * 5843 * 5849 * 5851 * 5857 * 5861 * 5867 * 5869 * 5879 * 5881 * 5897 * 5903 * 5923 * 5927 * 5939 * 5953 * 5981 * 5987 * 6007 * 6011 * 6029 * 6037 * 6043 * 6047 * 6053 * 6067 * 6073 * 6079 * 6089 * 6091 * 6101 * 6113 * 6121 * 6131 * 6133 * 6143 * 6151 * 6163 * 6173 * 6197 * 6199 * 6203 * 6211 * 6217 * 6221 * 6229 * 6247 * 6257 * 6263 * 6269 * 6271 * 6277 * 6287 * 6299 * 6301 * 6311 * 6317 * 6323 * 6329 * 6337 * 6343 * 6353 * 6359 * 6361 * 6367 * 6373 * 6379 * 6389 * 6397 * 6421 * 6427 * 6449 * 6451 * 6469 * 6473 * 6481 * 6491 * 6521 * 6529 * 6547 * 6551 * 6553 * 6563 * 6569 * 6571 * 6577 * 6581 * 6599 * 6607
https://ideone.com/ZZApk
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!