fork(3) download 
  1. #include <algorithm>
  2. #include <functional>
  3. #include <iostream>
  4. #include <iterator>
  5. #include <numeric>
  6. #include <utility>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. class Factor {
  12. 	vector<pair<unsigned int, size_t>> factors;
  13.  
  14. 	void factor(const unsigned int input) {
  15. 		auto i = 2U;
  16.  
  17. 		while (input % i != 0U) {
  18. 			++i;
  19. 		}
  20.  
  21. 		const auto second = input / i;
  22.  
  23. 		factors[input] = make_pair(i, second);
  24.  
  25. 		if (second >= 2 && factors[second].first == 0U) {
  26. 			factor(second);
  27. 		}
  28. 	}
  29. public:
  30. 	vector<unsigned int> getFactors(unsigned int input) {
  31. 		if (input <= 1) {
  32. 			return vector<unsigned int>{};
  33. 		} else if (input >= factors.size()) {
  34. 			factors.resize(input + 1U);
  35. 			factor(input);
  36. 		} else if (factors[input].first == 0U) {
  37. 			factor(input);
  38. 		}
  39.  
  40. 		vector<unsigned int> result;
  41.  
  42. 		do {
  43. 			result.push_back(factors[input].first);
  44. 			input = factors[input].second;
  45. 		} while (factors[input].first != 0U);
  46.  
  47. 		return result;
  48. 	}
  49.  
  50. 	size_t getFactorCount(const unsigned int input) {
  51. 		return getFactors(input).size();
  52. 	}
  53.  
  54. 	int compareFactors(const unsigned int lhs, const unsigned int rhs) {
  55. 		return getFactorCount(lhs) - getFactorCount(rhs);
  56. 	}
  57.  
  58. 	unsigned int findNextPrime(unsigned int input) {
  59. 		if (++input == 1U) {
  60. 			return 1U;
  61. 		}
  62.  
  63. 		do {
  64. 			if (input >= factors.size()) {
  65. 				factors.resize(input + 1U);
  66. 			}
  67.  
  68. 			if (factors[input].first == 0U) {
  69. 				factor(input);
  70. 			}
  71. 		} while (factors[input++].second != 1U);
  72.  
  73. 		return input - 1U;
  74. 	}
  75.  
  76. 	unsigned int gcd(const unsigned int lhs, const unsigned int rhs) {
  77. 		vector<unsigned int> result;
  78. 		const vector<unsigned int> lhsFactors = getFactors(lhs);
  79. 		const vector<unsigned int> rhsFactors = getFactors(rhs);
  80.  
  81. 		set_intersection(cbegin(lhsFactors), cend(lhsFactors), cbegin(rhsFactors), cend(rhsFactors), back_inserter(result));
  82.  
  83. 		return accumulate(cbegin(result), cend(result), 1U, multiplies<unsigned int>());
  84. 	}
  85.  
  86. 	unsigned int lcm(const unsigned int lhs, const unsigned int rhs) {
  87. 		const vector<unsigned int> lhsFactors = getFactors(lhs);
  88. 		const vector<unsigned int> rhsFactors = getFactors(rhs);
  89. 		const auto it = find_first_of(cbegin(lhsFactors), cend(lhsFactors), cbegin(rhsFactors), cend(rhsFactors));
  90.  
  91. 		return it == cend(lhsFactors) ? 1U : *it;
  92. 	}
  93. };
  94.  
  95. int main() {
  96. 	Factor factor;
  97.  
  98. 	for (auto i = 0U; i < 256U; ++i) {
  99. 		const auto factors = factor.getFactors(i);
  100.  
  101. 		cout << "\n\t" << i << '(' << factors.size() << "): ";
  102.  
  103. 		copy(cbegin(factors), cend(factors), ostream_iterator<unsigned int>(cout, " "));
  104. 	}
  105.  
  106. 	cout << "\n\ngetFactorCount(128): " << factor.getFactorCount(128U) << "\ncompareFactors(64, 128): " << factor.compareFactors(64U, 128U) << "\ncompareFactors(128, 64): " << factor.compareFactors(128U, 64U) << "\ncompareFactors(8, 27): " << factor.compareFactors(8U, 27U) << "\ngcd(12, 15): " << factor.gcd(12U, 15U) << "\nlcm(512, 13): " << factor.lcm(512U, 13U) << "\nfindNextPrime(11)" << factor.findNextPrime(11U) << endl;
  107. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin 
Standard input is empty
stdout 
	0(0): 
	1(0): 
	2(1): 2 
	3(1): 3 
	4(2): 2 2 
	5(1): 5 
	6(2): 2 3 
	7(1): 7 
	8(3): 2 2 2 
	9(2): 3 3 
	10(2): 2 5 
	11(1): 11 
	12(3): 2 2 3 
	13(1): 13 
	14(2): 2 7 
	15(2): 3 5 
	16(4): 2 2 2 2 
	17(1): 17 
	18(3): 2 3 3 
	19(1): 19 
	20(3): 2 2 5 
	21(2): 3 7 
	22(2): 2 11 
	23(1): 23 
	24(4): 2 2 2 3 
	25(2): 5 5 
	26(2): 2 13 
	27(3): 3 3 3 
	28(3): 2 2 7 
	29(1): 29 
	30(3): 2 3 5 
	31(1): 31 
	32(5): 2 2 2 2 2 
	33(2): 3 11 
	34(2): 2 17 
	35(2): 5 7 
	36(4): 2 2 3 3 
	37(1): 37 
	38(2): 2 19 
	39(2): 3 13 
	40(4): 2 2 2 5 
	41(1): 41 
	42(3): 2 3 7 
	43(1): 43 
	44(3): 2 2 11 
	45(3): 3 3 5 
	46(2): 2 23 
	47(1): 47 
	48(5): 2 2 2 2 3 
	49(2): 7 7 
	50(3): 2 5 5 
	51(2): 3 17 
	52(3): 2 2 13 
	53(1): 53 
	54(4): 2 3 3 3 
	55(2): 5 11 
	56(4): 2 2 2 7 
	57(2): 3 19 
	58(2): 2 29 
	59(1): 59 
	60(4): 2 2 3 5 
	61(1): 61 
	62(2): 2 31 
	63(3): 3 3 7 
	64(6): 2 2 2 2 2 2 
	65(2): 5 13 
	66(3): 2 3 11 
	67(1): 67 
	68(3): 2 2 17 
	69(2): 3 23 
	70(3): 2 5 7 
	71(1): 71 
	72(5): 2 2 2 3 3 
	73(1): 73 
	74(2): 2 37 
	75(3): 3 5 5 
	76(3): 2 2 19 
	77(2): 7 11 
	78(3): 2 3 13 
	79(1): 79 
	80(5): 2 2 2 2 5 
	81(4): 3 3 3 3 
	82(2): 2 41 
	83(1): 83 
	84(4): 2 2 3 7 
	85(2): 5 17 
	86(2): 2 43 
	87(2): 3 29 
	88(4): 2 2 2 11 
	89(1): 89 
	90(4): 2 3 3 5 
	91(2): 7 13 
	92(3): 2 2 23 
	93(2): 3 31 
	94(2): 2 47 
	95(2): 5 19 
	96(6): 2 2 2 2 2 3 
	97(1): 97 
	98(3): 2 7 7 
	99(3): 3 3 11 
	100(4): 2 2 5 5 
	101(1): 101 
	102(3): 2 3 17 
	103(1): 103 
	104(4): 2 2 2 13 
	105(3): 3 5 7 
	106(2): 2 53 
	107(1): 107 
	108(5): 2 2 3 3 3 
	109(1): 109 
	110(3): 2 5 11 
	111(2): 3 37 
	112(5): 2 2 2 2 7 
	113(1): 113 
	114(3): 2 3 19 
	115(2): 5 23 
	116(3): 2 2 29 
	117(3): 3 3 13 
	118(2): 2 59 
	119(2): 7 17 
	120(5): 2 2 2 3 5 
	121(2): 11 11 
	122(2): 2 61 
	123(2): 3 41 
	124(3): 2 2 31 
	125(3): 5 5 5 
	126(4): 2 3 3 7 
	127(1): 127 
	128(7): 2 2 2 2 2 2 2 
	129(2): 3 43 
	130(3): 2 5 13 
	131(1): 131 
	132(4): 2 2 3 11 
	133(2): 7 19 
	134(2): 2 67 
	135(4): 3 3 3 5 
	136(4): 2 2 2 17 
	137(1): 137 
	138(3): 2 3 23 
	139(1): 139 
	140(4): 2 2 5 7 
	141(2): 3 47 
	142(2): 2 71 
	143(2): 11 13 
	144(6): 2 2 2 2 3 3 
	145(2): 5 29 
	146(2): 2 73 
	147(3): 3 7 7 
	148(3): 2 2 37 
	149(1): 149 
	150(4): 2 3 5 5 
	151(1): 151 
	152(4): 2 2 2 19 
	153(3): 3 3 17 
	154(3): 2 7 11 
	155(2): 5 31 
	156(4): 2 2 3 13 
	157(1): 157 
	158(2): 2 79 
	159(2): 3 53 
	160(6): 2 2 2 2 2 5 
	161(2): 7 23 
	162(5): 2 3 3 3 3 
	163(1): 163 
	164(3): 2 2 41 
	165(3): 3 5 11 
	166(2): 2 83 
	167(1): 167 
	168(5): 2 2 2 3 7 
	169(2): 13 13 
	170(3): 2 5 17 
	171(3): 3 3 19 
	172(3): 2 2 43 
	173(1): 173 
	174(3): 2 3 29 
	175(3): 5 5 7 
	176(5): 2 2 2 2 11 
	177(2): 3 59 
	178(2): 2 89 
	179(1): 179 
	180(5): 2 2 3 3 5 
	181(1): 181 
	182(3): 2 7 13 
	183(2): 3 61 
	184(4): 2 2 2 23 
	185(2): 5 37 
	186(3): 2 3 31 
	187(2): 11 17 
	188(3): 2 2 47 
	189(4): 3 3 3 7 
	190(3): 2 5 19 
	191(1): 191 
	192(7): 2 2 2 2 2 2 3 
	193(1): 193 
	194(2): 2 97 
	195(3): 3 5 13 
	196(4): 2 2 7 7 
	197(1): 197 
	198(4): 2 3 3 11 
	199(1): 199 
	200(5): 2 2 2 5 5 
	201(2): 3 67 
	202(2): 2 101 
	203(2): 7 29 
	204(4): 2 2 3 17 
	205(2): 5 41 
	206(2): 2 103 
	207(3): 3 3 23 
	208(5): 2 2 2 2 13 
	209(2): 11 19 
	210(4): 2 3 5 7 
	211(1): 211 
	212(3): 2 2 53 
	213(2): 3 71 
	214(2): 2 107 
	215(2): 5 43 
	216(6): 2 2 2 3 3 3 
	217(2): 7 31 
	218(2): 2 109 
	219(2): 3 73 
	220(4): 2 2 5 11 
	221(2): 13 17 
	222(3): 2 3 37 
	223(1): 223 
	224(6): 2 2 2 2 2 7 
	225(4): 3 3 5 5 
	226(2): 2 113 
	227(1): 227 
	228(4): 2 2 3 19 
	229(1): 229 
	230(3): 2 5 23 
	231(3): 3 7 11 
	232(4): 2 2 2 29 
	233(1): 233 
	234(4): 2 3 3 13 
	235(2): 5 47 
	236(3): 2 2 59 
	237(2): 3 79 
	238(3): 2 7 17 
	239(1): 239 
	240(6): 2 2 2 2 3 5 
	241(1): 241 
	242(3): 2 11 11 
	243(5): 3 3 3 3 3 
	244(3): 2 2 61 
	245(3): 5 7 7 
	246(3): 2 3 41 
	247(2): 13 19 
	248(4): 2 2 2 31 
	249(2): 3 83 
	250(4): 2 5 5 5 
	251(1): 251 
	252(5): 2 2 3 3 7 
	253(2): 11 23 
	254(2): 2 127 
	255(3): 3 5 17 

getFactorCount(128): 7
compareFactors(64, 128): -1
compareFactors(128, 64): 1
compareFactors(8, 27): 0
gcd(12, 15): 3
lcm(512, 13): 1
findNextPrime(11)13
https://ideone.com/njH34A
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!