Can you write a program in c plus plus for finding practical numbers?

Answer 1

#include<iostream>

#include<vector>

#include<sstream>

#include<cassert>

using set_type = std::vector<size_t>;

using set_const_iterator = set_type::const_iterator;

using subset_type = std::vector<set_type::const_iterator>;

using subset_const_iterator = subset_type::const_iterator;

using subset_reverse_iterator = subset_type::reverse_iterator;

// Returns the first subset of the given set with the given count.

subset_type first_subset (const set_type& set, size_t count)

{

assert (0U < count);

assert (count <= set.size());

subset_type subset;

for (set_const_iterator it=set.begin(); count--; ++it)

subset.push_back (it);

return subset;

}

// Returns the next subset after the given subset of the given set with the given count.

subset_type next_subset (set_type& set, size_t count, subset_type subset)

{

assert (subset.size() == count);

if (count)

{

subset_reverse_iterator sub_it = subset.rbegin();

set_const_iterator set_it = *sub_it;

subset.pop_back();

if (++set_it != set.end())

subset.push_back (set_it);

else if (1U != count)

{

const size_t value = set.back();

set.pop_back();

subset = next_subset(set, --count, subset);

set.push_back (value);

if (subset.size() == count++)

{

sub_it = subset.rbegin();

set_it = *sub_it;

if (++set_it != set.end())

subset.push_back (set_it);

}

}

}

return subset;

}

// Returns all the divisors of the given number.

set_type get_divisors (const size_t num)

{

set_type divs;

size_t factor = 0;

while (factor++<=num/2)

{

if (num%factor==0)

divs.push_back (factor);

}

return divs;

}

// Returns the sum of the given subset.

size_t sum (const subset_type& subset)

{

size_t sum = 0;

for (subset_const_iterator it=subset.begin(); it!=subset.end(); sum += **it, ++it);

return sum;

}

// Returns true if the sum of any combination of distinct divisors totals the given number

bool has_compound (const size_t num, set_type divisors)

{

bool found = false;

for (size_t count=1; !found && count<=divisors.size(); ++count)

for (subset_type subset = first_subset (divisors, count); !found && subset.size(); subset = next_subset (divisors, count, subset))

found = sum (subset) == num;

return found;

}

// Returns true if the given number is a practical number.

bool is_practical (const size_t num)

{

if (!num) return false;

if (num<3) return true;

if (num%2) return false;

set_type divs = get_divisors (num);

for (size_t val=1; val<num; ++val)

if (!has_compound (val, divs))

return false;

return true;

}

int main()

{

std::cout << "Practical numbers in the range 1 to 240\n\n";

std::stringstream ss;

for (size_t num=1; num<=240; ++num)

{

if (is_practical(num))

{

if (ss.str().size())

ss << ", ";

ss << num;

std::cout << num << std::endl;

}

}

// Assert that the numbers match those in sequence A005153

// of the Online Encyclopedia of Integer Sequences (OEIS).

std::string verify = "1, 2, 4, 6, 8, 12, 16, 18, 20, 24, "

"28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72, 78, "

"80, 84, 88, 90, 96, 100, 104, 108, 112, 120, 126, 128, "

"132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, "

"196, 198, 200, 204, 208, 210, 216, 220, 224, 228, 234, 240";

std::cout << verify << std::endl;

std::cout << ss.str() << std::endl;

assert (ss.str() == verify);

}