Practical numbers: Difference between revisions

Content added Content deleted
(Added C++ solution)
m (C++ performance improvement)
Line 72: Line 72:
#include <vector>
#include <vector>


// Returns true if any subset of f sums to n.
// Returns true if any subset of [begin, end) sums to n.
template <typename iterator>
bool sum_of_any_subset(int n, const std::vector<int>& f) {
bool sum_of_any_subset(int n, iterator begin, iterator end) {
if (f.empty())
if (begin == end)
return false;
return false;
if (std::find(f.begin(), f.end(), n) != f.end())
if (std::find(begin, end, n) != end)
return true;
return true;
int total = std::accumulate(f.begin(), f.end(), 0);
int total = std::accumulate(begin, end, 0);
if (n == total)
if (n == total)
return true;
return true;
if (n > total)
if (n > total)
return false;
return false;
int d = n - f.back();
--end;
std::vector<int> g(f.begin(), f.end() - 1);
int d = n - *end;
return std::find(g.begin(), g.end(), d) != g.end() ||
return (d > 0 && sum_of_any_subset(d, begin, end)) ||
(d > 0 && sum_of_any_subset(d, g)) || sum_of_any_subset(n, g);
sum_of_any_subset(n, begin, end);
}
}


Line 106: Line 107:
std::vector<int> f = factors(n);
std::vector<int> f = factors(n);
for (int i = 1; i < n; ++i) {
for (int i = 1; i < n; ++i) {
if (!sum_of_any_subset(i, f))
if (!sum_of_any_subset(i, f.begin(), f.end()))
return false;
return false;
}
}
Line 136: Line 137:
std::cout << "Found " << practical.size() << " practical numbers:\n"
std::cout << "Found " << practical.size() << " practical numbers:\n"
<< shorten(practical, 10) << '\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) << '\n';
<< "a practical number.\n";
return 0;
return 0;
}</lang>
}</lang>
Line 144: Line 145:
{{out}}
{{out}}
<pre>
<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
1, 2, 4, 6, 8, 12, 16, 18, 20, 24, ..., 288, 294, 300, 304, 306, 308, 312, 320, 324, 330
⚫
666 is a practical 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>
</pre>


Retrieved from "https://rosettacode.org/wiki/Practical_numbers"