Rosetta Code

Practical numbers: Difference between revisions

Page Discussion

Practical numbers (view source)

Revision as of 11:50, 3 May 2021

3 bytes added ,  3 years ago
m
C++ performance improvement
(Added C++ solution)
m (C++ performance improvement)
Line 72:
#include <vector>
 
// Returns true if any subset of f[begin, end) sums to n.
template <typename iterator>
bool sum_of_any_subset(int n, constiterator std::vector<int>&begin, fiterator end) {
if (f.empty()begin == end)
return false;
if (std::find(f.begin(), f.end(), n) != f.end())
return true;
int total = std::accumulate(f.begin(), f.end(), 0);
if (n == total)
return true;
if (n > total)
return false;
int d = n - f.back()-end;
std::vector<int> g(f.begin(),d f.end()= n - 1)*end;
return std::find(g.begind > 0 && sum_of_any_subset()d, g.end()begin, dend) != g.end() ||
(d > 0 && sum_of_any_subset(dn, g)) || sum_of_any_subset(nbegin, gend);
}
 
Line 106 ⟶ 107:
std::vector<int> f = factors(n);
for (int i = 1; i < n; ++i) {
if (!sum_of_any_subset(i, f.begin(), f.end()))
return false;
}
Line 136 ⟶ 137:
std::cout << "Found " << practical.size() << " practical numbers:\n"
<< shorten(practical, 10) << '\n';
for (int n : {666, 6666, 66666, 672, 720, 222222})▼
std::cout << std::boolalpha;
std::cout << n << " is " << (is_practical(n) ? "" : "not ")
▲ for (int n : {666, 6666, 66666, 672, 720})
std::cout << "is_practical(" << n << "): " << is_practical(n) << '"a practical number.\n'";
return 0;
}</lang>
Line 144 ⟶ 145:
{{out}}
<pre>
Found 77 practical numbers:▼
1, 2, 4, 6, 8, 12, 16, 18, 20, 24, ..., 288, 294, 300, 304, 306, 308, 312, 320, 324, 330
▲Found666 77is a practical numbers:number.
is_practical(666): true
6666 is a practical number.
is_practical(6666): true
66666 is not a practical number.
is_practical(66666): false
672 is a practical number.
is_practical(672): true
720 is a practical number.
is_practical(720): true
222222 is a practical number.
</pre>
 
Simonjsaunders
1,777

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/310371"