#include <iostream>
#include <vector>
using namespace std;

// Function to calculate the smallest prime factors (SPF)
vector<int> calculate_spf(int n) {
    vector<int> SPF(n + 1, 0); // SPF array initialized to 0

    for (int i = 2; i <= n; i++) {
        if (SPF[i] == 0) { // i is a prime number
            for (int j = i; j <= n; j += i) {
                if (SPF[j] == 0) { // Mark only if not marked
                    SPF[j] = i; // Assign smallest prime factor
                }
            }
        }
    }
    return SPF;
}

// Function to get the prime factors of a number using the SPF array
vector<int> get_prime_factors(int n, const vector<int>& SPF) {
    vector<int> prime_factors;
    while (n != 1) {
        prime_factors.push_back(SPF[n]);
        n /= SPF[n]; // Divide n by its smallest prime factor
    }
    return prime_factors;
}

int main() {
    int N = 100; // Precompute SPF array for numbers up to N
    vector<int> SPF = calculate_spf(N);

    // Example: Factorizing multiple numbers
    vector<int> numbers_to_factor = {30, 45, 84, 97};

    for (int num : numbers_to_factor) {
        cout << "Prime factors of " << num << ": ";
        vector<int> factors = get_prime_factors(num, SPF);
        for (int f : factors) {
            cout << f << " ";
        }
        cout << endl;
    }

    return 0;
}