How to resolve the algorithm Partition an integer x into n primes step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm Partition an integer x into n primes step by step in the C++ programming language

Table of Contents

Problem Statement

Partition a positive integer   X   into   N   distinct primes.

Or, to put it in another way: Find   N   unique primes such that they add up to   X.

Show in the output section the sum   X   and the   N   primes in ascending order separated by plus (+) signs: The output could/should be shown in a format such as: This task is similar to factoring an integer.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Partition an integer x into n primes step by step in the C++ programming language

Initialization:

  • init(): Initializes static data by generating the first 50,000 prime numbers and storing them in the primes vector.

Core Logic:

  • findCombo():

    • Recursive function that tries to find a combination of prime numbers that sums up to x, using at most m numbers.
    • It explores all possible combinations by iterating through the range of primes and recursively calling itself.
    • Returns true if a valid combination is found, otherwise false.

  • partition():

    • Partitions a number x into a sum of m primes.
    • It checks for invalid input and filters out primes greater than x.
    • If there are enough primes available, it calls findCombo() to try to find a valid combination.
    • If no combination is found, it prints a message indicating that it's not possible to partition x with m primes.

Usage:

  • main():
    • Initializes the program by calling init().
    • Reads a set of numbers and their desired number of partitions from a predefined list.
    • For each pair of numbers, it tries to partition the number using the specified number of partitions and prints the result or a message stating that it's not possible.

Class and Helper Functions:

  • Seq:

    • A sequence that iterates over prime numbers, starting from 2 and skipping even numbers (except 2).
    • It provides methods to check if it's empty and to get the current prime number.
    • It also has a helper method isPrime() to check if a number is prime.

  • isPrime():

    • An optimized function to check if a number is prime. It skips checking all even numbers except 2 and uses the Fermat Little Theorem for efficiency.

  • copy_if():

    • A standard library function that copies elements from a range that satisfy a given condition. It's used to filter out primes greater than x in the partition() function.

Source code in the cpp programming language

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

std::vector<int> primes;

struct Seq {
public:
    bool empty() {
        return p < 0;
    }

    int front() {
        return p;
    }

    void popFront() {
        if (p == 2) {
            p++;
        } else {
            p += 2;
            while (!empty() && !isPrime(p)) {
                p += 2;
            }
        }
    }

private:
    int p = 2;

    bool isPrime(int n) {
        if (n < 2) return false;
        if (n % 2 == 0) return n == 2;
        if (n % 3 == 0) return n == 3;

        int d = 5;
        while (d * d <= n) {
            if (n % d == 0) return false;
            d += 2;
            if (n % d == 0) return false;
            d += 4;
        }
        return true;
    }
};

// generate the first 50,000 primes and call it good
void init() {
    Seq seq;

    while (!seq.empty() && primes.size() < 50000) {
        primes.push_back(seq.front());
        seq.popFront();
    }
}

bool findCombo(int k, int x, int m, int n, std::vector<int>& combo) {
    if (k >= m) {
        int sum = 0;
        for (int idx : combo) {
            sum += primes[idx];
        }

        if (sum == x) {
            auto word = (m > 1) ? "primes" : "prime";
            printf("Partitioned %5d with %2d %s ", x, m, word);
            for (int idx = 0; idx < m; ++idx) {
                std::cout << primes[combo[idx]];
                if (idx < m - 1) {
                    std::cout << '+';
                } else {
                    std::cout << '\n';
                }
            }
            return true;
        }
    } else {
        for (int j = 0; j < n; j++) {
            if (k == 0 || j > combo[k - 1]) {
                combo[k] = j;
                bool foundCombo = findCombo(k + 1, x, m, n, combo);
                if (foundCombo) {
                    return true;
                }
            }
        }
    }

    return false;
}

void partition(int x, int m) {
    if (x < 2 || m < 1 || m >= x) {
        throw std::runtime_error("Invalid parameters");
    }

    std::vector<int> filteredPrimes;
    std::copy_if(
        primes.cbegin(), primes.cend(),
        std::back_inserter(filteredPrimes),
        [x](int a) { return a <= x; }
    );

    int n = filteredPrimes.size();
    if (n < m) {
        throw std::runtime_error("Not enough primes");
    }

    std::vector<int> combo;
    combo.resize(m);
    if (!findCombo(0, x, m, n, combo)) {
        auto word = (m > 1) ? "primes" : "prime";
        printf("Partitioned %5d with %2d %s: (not possible)\n", x, m, word);
    }
}

int main() {
    init();

    std::vector<std::pair<int, int>> a{
        {99809,  1},
        {   18,  2},
        {   19,  3},
        {   20,  4},
        { 2017, 24},
        {22699,  1},
        {22699,  2},
        {22699,  3},
        {22699,  4},
        {40355,  3}
    };

    for (auto& p : a) {
        partition(p.first, p.second);
    }

    return 0;
}

You may also check:How to resolve the algorithm Variadic function step by step in the Scala programming language
You may also check:How to resolve the algorithm Unprimeable numbers step by step in the Perl programming language
You may also check:How to resolve the algorithm Function prototype step by step in the Ada programming language
You may also check:How to resolve the algorithm Arrays step by step in the jq programming language
You may also check:How to resolve the algorithm URL decoding step by step in the Elixir programming language