溫馨提示×

C++分解質(zhì)因數(shù)的遞歸和非遞歸方法

c++
小樊
88
2024-07-14 08:04:29
欄目: 編程語言

非遞歸方法：

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

void primeFactors(int n) {
    vector<int> factors;
    for (int i = 2; i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }

    for (int i = 0; i < factors.size(); i++) {
        cout << factors[i];
        if (i != factors.size() - 1) {
            cout << " * ";
        }
    }
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;

    cout << "Prime factors of " << n << " are: ";
    primeFactors(n);

    return 0;
}

遞歸方法：

#include <iostream>
using namespace std;

void primeFactors(int n, int i) {
    if (n <= 1) {
        return;
    }

    while (n % i != 0) {
        i++;
    }

    cout << i;
    if (n != i) {
        cout << " * ";
    }

    primeFactors(n / i, i);
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;

    cout << "Prime factors of " << n << " are: ";
    primeFactors(n, 2);

    return 0;
}

0 踩