Question

How to find a number that can be written as the sum and product of its factors in C++

Answer 1

#include <iostream>
#include <vector>
#include <numeric>

std::vector<int> primeFactors(int n) {
    std::vector<int> f;
    for (int p = 2; p * p <= n; p++) {
        while (n % p == 0) {
            f.push_back(p);
            n /= p;
        }
    }
    if (n > 1) f.push_back(n);
    
    return f;
}

bool isSumProduct(int n, std::vector<int>& outFactors) {
    auto f = primeFactors(n);

    long long product = std::accumulate(f.begin(), f.end(), 1LL,
        [](long long a, long long b) { return a * b; });

    long long sum = std::accumulate(f.begin(), f.end(), 0LL);

    // Add 1's until sum == product
    while (sum < product) {
        f.push_back(1);
        sum += 1;
    }

    if (sum == product) {
        outFactors = f;
        return true;
    }
    
    return false;
}

int main() {
    for (int n = 5; n <= 14; n++) {
        std::vector<int> factors;
        if (isSumProduct(n, factors) && factors.size() > 1) {
            std::cout << n << " = ";
            for (size_t i = 0; i < factors.size(); i++) {
                std::cout << factors[i];
                if (i + 1 < factors.size()) std::cout << " * ";
            }
            std::cout << " = ";
            for (size_t i = 0; i < factors.size(); i++) {
                std::cout << factors[i];
                if (i + 1 < factors.size()) std::cout << " + ";
            }
            std::cout << " = ";
            long long sum = std::accumulate(factors.begin(), factors.end(), 0LL);
            std::cout << sum << "\n";
        }
    }
}



/*
run:

6 = 2 * 3 * 1 = 2 + 3 + 1 = 6
8 = 2 * 2 * 2 * 1 * 1 = 2 + 2 + 2 + 1 + 1 = 8
9 = 3 * 3 * 1 * 1 * 1 = 3 + 3 + 1 + 1 + 1 = 9
10 = 2 * 5 * 1 * 1 * 1 = 2 + 5 + 1 + 1 + 1 = 10
12 = 2 * 2 * 3 * 1 * 1 * 1 * 1 * 1 = 2 + 2 + 3 + 1 + 1 + 1 + 1 + 1 = 12
14 = 2 * 7 * 1 * 1 * 1 * 1 * 1 = 2 + 7 + 1 + 1 + 1 + 1 + 1 = 14

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

std::vector<int> divisors(int n) {
    std::vector<int> d;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            d.push_back(i);
            if (i != n / i)
                d.push_back(n / i);
        }
    }
    std::sort(d.begin(), d.end());
    
    return d;
}

bool isSumProduct(int n, std::vector<int>& outFactors) {
    auto d = divisors(n);

    // Choose the largest non-trivial factor pair (a, b)
    int a = 1, b = n;
    for (int x : d) {
        if (x != 1 && x != n && n % x == 0) {
            a = x;
            b = n / x;
        }
    }

    std::vector<int> f = {a, b};

    long long product = a * b;
    long long sum = a + b;

    // Add 1's until sum == product
    while (sum < product) {
        f.push_back(1);
        sum += 1;
    }

    if (sum == product) {
        outFactors = f;
        return true;
    }

    return false;
}

int main() {
    for (int n = 5; n <= 14; n++) {
        std::vector<int> factors;
        if (isSumProduct(n, factors)) {
            std::cout << n << " = ";

            for (size_t i = 0; i < factors.size(); i++) {
                std::cout << factors[i];
                if (i + 1 < factors.size()) std::cout << " * ";
            }

            std::cout << " = ";

            for (size_t i = 0; i < factors.size(); i++) {
                std::cout << factors[i];
                if (i + 1 < factors.size()) std::cout << " + ";
            }

            std::cout << " = "
                      << std::accumulate(factors.begin(), factors.end(), 0LL)
                      << "\n";
        }
    }
}


 
/*
run:
 
6 = 3 * 2 * 1 = 3 + 2 + 1 = 6
8 = 4 * 2 * 1 * 1 = 4 + 2 + 1 + 1 = 8
9 = 3 * 3 * 1 * 1 * 1 = 3 + 3 + 1 + 1 + 1 = 9
10 = 5 * 2 * 1 * 1 * 1 = 5 + 2 + 1 + 1 + 1 = 10
12 = 6 * 2 * 1 * 1 * 1 * 1 = 6 + 2 + 1 + 1 + 1 + 1 = 12
14 = 7 * 2 * 1 * 1 * 1 * 1 * 1 = 7 + 2 + 1 + 1 + 1 + 1 + 1 = 14
 
*/

 

70+ SQL courses for beginners and professionals