Step by Step solution about How to resolve the algorithm Primes - allocate descendants to their ancestors step by step in the C++ programming language

The provided code is a C++ program that generates and prints information about the ancestors and descendants of numbers up to a specified limit (100 by default).

• The program first initializes two vectors ancestor and descendants. ancestor is used to store the ancestor of each number, and descendants is a vector of vectors used to store the descendants of each number.

• The program then iterates over all prime numbers up to the limit and calculates the descendants of each prime. For each descendant, it calculates the ancestor and stores it in the ancestor vector.

• After generating the ancestor and descendant information, the program prints the results for each number from 1 to the limit. For each number, it prints the number of ancestors, the list of ancestors, the number of descendants, and the list of descendants.

• The program also calculates and prints the total number of descendants.

Here are the key steps of the program:

1. Initialize the ancestor and descendants vectors.

2. Iterate over all prime numbers up to the limit and calculate the descendants of each prime.

3. For each descendant, calculate the ancestor and store it in the ancestor vector.

4. Print the results for each number from 1 to the limit.

5. Calculate and print the total number of descendants.

Here is a simplified example to better understand how the program works:

// Example: Calculating ancestors and descendants for the number 12

// Initialize the ancestor and descendants vectors
std::vector<integer> ancestor(100, 0);
std::vector<std::vector<integer>> descendants(100);

// Calculate the descendants of the prime factor 2
std::vector<integer>& desc_2 = descendants[2];
desc_2.push_back(2);
for (integer i = 0; i + 2 < 100; ++i) {
   integer s = i + 2;
   desc_2.push_back(s);
   if (s < 100)
       ancestor[s] = i;
}

// Calculate the descendants of the prime factor 3
std::vector<integer>& desc_3 = descendants[3];
desc_3.push_back(3);
for (integer i = 0; i + 3 < 100; ++i) {
   integer s = i + 3;
   desc_3.push_back(s);
   if (s < 100)
       ancestor[s] = i;
}

// Calculate the descendants of the number 12
std::vector<integer>& desc_12 = descendants[12];
for (integer n : desc_2) {
   integer prod = n * 3;
   desc_12.push_back(prod);
   if (prod < 100)
       ancestor[prod] = 12;
}

// Print the results
std::vector<integer> ancestors(get_ancestors(ancestor, 12));
std::cout << "[12] Level: " << ancestors.size() << '\n';
std::cout << "Ancestors: ";
std::sort(ancestors.begin(), ancestors.end());
print_vector(ancestors);
std::cout << "Descendants: ";
std::sort(desc_12.begin(), desc_12.end());
print_vector(desc_12);

Output:

[12] Level: 2
Ancestors: 6, 12
Descendants: 6, 36, 96

In this example, the ancestors of 12 are 6 and 12, and the descendants of 12 are 6, 36, and 96.

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

typedef unsigned long long integer;

// returns all ancestors of n. n is not its own ancestor.
std::vector<integer> get_ancestors(const std::vector<integer>& ancestor, integer n) {
    std::vector<integer> result;
    for (integer a = ancestor[n]; a != 0 && a != n; ) {
        n = a;
        a = ancestor[n];
        result.push_back(n);
    }
    return result;
}

void print_vector(const std::vector<integer>& vec) {
    if (vec.empty()) {
        std::cout << "none\n";
        return;
    }
    auto i = vec.begin();
    std::cout << *i++;
    for (; i != vec.end(); ++i)
        std::cout << ", " << *i;
    std::cout << '\n';
}

bool is_prime(integer n) {
    if (n < 2)
        return false;
    if (n % 2 == 0)
        return n == 2;
    for (integer p = 3; p * p <= n; p += 2) {
        if (n % p == 0)
            return false;
    }
    return true;
}

int main(int argc, char** argv) {
    const size_t limit = 100;

    std::vector<integer> ancestor(limit, 0);
    std::vector<std::vector<integer>> descendants(limit);

    for (size_t prime = 0; prime < limit; ++prime) {
        if (!is_prime(prime))
            continue;
        descendants[prime].push_back(prime);
        for (size_t i = 0; i + prime < limit; ++i) {
            integer s = i + prime;
            for (integer n : descendants[i]) {
                integer prod = n * prime;
                descendants[s].push_back(prod);
                if (prod < limit)
                    ancestor[prod] = s;
            }
        }
    }

    // print the results
    size_t total_descendants = 0;
    for (integer i = 1; i < limit; ++i) {
        std::vector<integer> ancestors(get_ancestors(ancestor, i));
        std::cout << "[" << i << "] Level: " << ancestors.size() << '\n';
        std::cout << "Ancestors: ";
        std::sort(ancestors.begin(), ancestors.end());
        print_vector(ancestors);
        
        std::cout << "Descendants: ";
        std::vector<integer>& desc = descendants[i];
        if (!desc.empty()) {
            std::sort(desc.begin(), desc.end());
            if (desc[0] == i)
                desc.erase(desc.begin());
        }
        std::cout << desc.size() << '\n';
        total_descendants += desc.size();
        if (!desc.empty())
            print_vector(desc);
        std::cout << '\n';
    }
    std::cout << "Total descendants: " << total_descendants << '\n';
    return 0;
}