Question

How to find numbers expressible as the sum of a prime square, cube, and prime fourth power in C++

Answer 1

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm> // std::max

std::vector<int> sieve(int n) {
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int p = 2; p * p <= n; ++p) {
        if (is_prime[p]) {
            for (int q = p * p; q <= n; q += p)
                is_prime[q] = false;
        }
    }

    std::vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i]) primes.push_back(i);

    return primes;
}

int main() {
    const int LIMIT = 100;   // adjust as needed

    int max_p2 = std::sqrt(LIMIT);
    int max_p3 = std::cbrt(LIMIT);
    int max_p4 = std::pow(LIMIT, 0.25);

    int max_base = std::max({max_p2, max_p3, max_p4});
    std::vector<int> primes = sieve(max_base);

    struct Term { int value, base, power; };
    std::vector<Term> p2, p3, p4;

    for (int p : primes) {
        int a = p * p;
        if (a < LIMIT) p2.push_back({a, p, 2});

        int b = a * p;
        if (b < LIMIT) p3.push_back({b, p, 3});

        int c = b * p;
        if (c < LIMIT) p4.push_back({c, p, 4});
    }

    std::vector<int> seen(LIMIT, 0);

    for (auto &A : p2) {
        for (auto &B : p3) {
            if (A.value + B.value >= LIMIT) break;
            for (auto &C : p4) {
                int s = A.value + B.value + C.value;
                if (s >= LIMIT) break;

                if (!seen[s]) {
                    seen[s] = 1;
                    std::cout << s << " = "
                              << A.base << "^" << A.power << " + "
                              << B.base << "^" << B.power << " + "
                              << C.base << "^" << C.power << "\n";
                }
            }
        }
    }
}



/*
run:

28 = 2^2 + 2^3 + 2^4
93 = 2^2 + 2^3 + 3^4
47 = 2^2 + 3^3 + 2^4
33 = 3^2 + 2^3 + 2^4
98 = 3^2 + 2^3 + 3^4
52 = 3^2 + 3^3 + 2^4
49 = 5^2 + 2^3 + 2^4
68 = 5^2 + 3^3 + 2^4
73 = 7^2 + 2^3 + 2^4
92 = 7^2 + 3^3 + 2^4

*/

 

70+ SQL courses for beginners and professionals