Cerința

Se dă un număr natural s. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe s ca produs de divizori proprii distincți ai lui s.

Date de intrare

Programul citește de la tastatură numărul s.

Date de ieșire

Programul va afișa pe ecran pe fiecare linie câte un şir de numere naturale ordonate strict crescător, separate prin câte un spaţiu. Produsul numerelor din fiecare şir este s, iar numerele sunt divizori proprii ai lui s. Şirurile vor fi afişate în ordine lexicografică.

Dacă numărul s nu poate fi scris ca produs de divizori proprii, se va fişa mesajul NU EXISTA.

Restricții și precizări

• 2 ≤ s ≤ 2000000000

Exemplu

Intrare

30

Ieșire

2 3 5 
2 15 
3 10 
5 6 

#include <bits/stdc++.h>

using namespace std;

int nr , a[500] , x[500] , n , ok;

void afisare(int k)
{
    for(int i = 1 ; i <= k ; i++)
        cout << a[x[i]] << " ";
    cout << '\n';
    ok++;
}

void back(int k, long long p)
{
    for(int i = x[k - 1] + 1 ; i <= n && p * a[i] <= nr ; i++)
    {
        x[k] = i;
        p *= a[x[k]];
        if(p <= nr)
            if(p == nr) afisare(k);
            else back(k + 1 , p);
        p /= a[x[k]];
    }
}

int main()
{
    cin >> nr;
    for(int i = 2 ; i * i <= nr ; i++)
        if(nr % i == 0)
        {
            a[++n] = i;
            if(i * i != nr)  a[++n] = nr / i;
        }
    sort(a + 1 , a + n + 1);
    back(1 , 1);
    if(ok == 0) cout << "NU EXISTA";
    return 0;
}